asd.py

import re
import sys

line1, line2 = open(sys.argv[1]).read().split(';')


def int2bin(n, count=24):
    """returns the binary of integer n, using count number of digits"""
    return "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])

n = 2**len(line1)

subsequences = []
for i in reversed(xrange(n)):
    susbseq = ''
    bin = int2bin(i, len(line1))
    subsec = ''.join(line1[i] for i,c in enumerate(bin) if int(c))
    subsequences.append(subsec)

subsequences.sort(lambda x,y: len(y)-len(x))

for subsec in subsequences:
    match = re.search('.*'.join([c for c in subsec]), line2)
    if match:
        print subsec
        exit()