LCS.py

def LongestCommonSubstring(S1, S2):
    M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
    longest, x_longest = 0, 0
    for x in xrange(1,1+len(S1)):
        for y in xrange(1,1+len(S2)):
            if S1[x-1] == S2[y-1]:
                M[x][y] = M[x-1][y-1] + 1
                if M[x][y]>longest:
                    longest = M[x][y]
                    x_longest  = x
            else:
                M[x][y] = 0
    return S1[x_longest-longest: x_longest]

if __name__ == '__main__':
    output = LongestCommonSubstring("^PRCA(430.2,0)=\"ACCOUNTS RECEIVABLE CATEGORY^430.2I^44^43\"",
                                    "^PRCA(430.2,39,0)=\"NURSING HOME CARE-LTC^NL^0^1319^^P^46^2^1^1^1^1^2^30,40,55,80\"")
    print output
    "Test".startswith(prefix)