#!/usr/bin/env python3

import sys


def main():
    if len(sys.argv) > 2:
        s = sys.argv[1]
        t = sys.argv[2]
    else:
        s = "yywzxyx"
        t = "xxyzywxy"
    m = len(s)
    n = len(t)
    c = [[0]*(n+1) for row in range(m+1)]
    b = [[0]*(n+1) for row in range(m+1)]
    print("s =", s)
    print("t =", t)
    program(s, t, b, c)
    answer = c[m][n]
    for i in range(m+1):
        for j in range(n+1):
            if c[i][j] == answer and b[i][j] == 1:
                lcs = find_solution(s, t, b, i, j)
                print(lcs + "  (" + str(i) + ", " + str(j) + ")")
    print("length =", str(answer))


def program(s, t, b, c):
    for i in range(len(c)):
        c[i][0] = 0
    for j in range(len(c[0])):
        c[0][j] = 0
    for i in range(1, len(c)):
        for j in range(1, len(c[0])):
            if s[i-1] == t[j-1]:
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 1  # increase lcs
            elif c[i-1][j] > c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = 2  # same column
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = 3  # same row


def find_solution(s, t, b, i, j):
    revlcs = ""
    while i > 0 and j > 0:
        if b[i][j] == 1:
            i = i - 1
            j = j - 1
            if s[i] != t[j]:
                raise ValueError("Solution mismatch", i, j)
            revlcs += s[i]
        elif b[i][j] == 2:
            i = i - 1
        elif b[i][j] == 3:
            j = j - 1
        else:
            raise ValueError("Table mismatch", i, j)
    return revlcs[::-1]  # reverse - lcs


if __name__ == '__main__':
    main()