[最长公共子串]#python

lccs.py

def lccs(a, b):
    flag = True
    if len(a) > len(b):
        a, b = b, a
        flag = False
    ret = ''
    sigma = 0
    last_position = 0
    dp = [[0]*(len(b)+1) for i in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > sigma:
                    if flag:
                        ret = b[j-dp[i][j] : j]
                        sigma = len(ret)
                        last_position = j - 1
                    else:
                        ret = a[i-dp[i][j]: i]
                        sigma = len(ret)
                        last_position = i - 1
    return ret, sigma, last_position