def lcs_len(a,b):

    c = [[0 for j in b] for i in a]

    for i in range(len(a)):

        for j in range(len(b)):

            if i==0 or j==0:

                continue

            if a[i]==b[j]:

                c[i][j] = c[i-1][j-1]+1

            else:

                c[i][j] = max(c[i-1][j],c[i][j-1])

    return c[i][j]

def lcs_string(a,b):

    lena,lenb = len(a),len(b)

    # length table

    c = [[0 for i in b] for j in a]

    # direction table

    flag = [[0 for i in b] for j in a]

    for i in range(lena):

        for j in range(lenb):

            if i==0 or j==0:           continue

            if a[i]==b[j]:

                c[i][j] = c[i-1][j-1]+1

                flag[i][j] = 3

            elif c[i-1][j]<c[i][j-1]:

                c[i][j] = c[i][j-1]

                flag[i][j] = 2

            else:

                c[i][j] = c[i-1][j]

                flag[i][j] = 1

    (p1,p2) = (lena-1,lenb-1)

    s = []

    while 1:

        d = flag[p1][p2]

        if d == 3:

            s.append(a[p1])

            p1 -= 1

            p2 -= 1

        elif d == 2:

            p2 -= 1

        elif d == 1:

            p1 -= 1

        if p1==0 or p2==0:

            # solve the first element without print problem

            if a[p1]==b[p2]:

                s.append(a[p1])

            break

    s.reverse()

    return ''.join(s)

def lcs_from_list(input,jobnames):

    if input in jobnames:

        return input

    res = [(lcs_len(input,jobname),jobname) for jobname in jobnames]

    res.sort()

    return res[-1][1]