动态规划之最长公共子串问题

def LongestCommonSubstring(X, Y):
    lm = 0               ## 最长子串长度
    pm = 0               ## 最长子串末尾
    c = [[0 for i in range(len(Y)+1)]for i in range(len(X)+1)]    ## 初始化表格
    for i in range(1,len(X)+1):                     
        for j in range(1,len(Y)+1):
            if(X[i-1] != Y[j-1]):            ## 因为xy列表是从0开始存的，所以开始i=1时对应0的位置
                c[i][j] = 0                 
            else:
                c[i][j] = c[i-1][j-1]+1 
                if(c[i][j] > lm):
                    lm = c[i][j]
                    pm = i
    print("最长子串长度为：{0}n从X数组的第{1}位数开始。".format(lm,pm-lm+1))

调用：

X = ['A','B','C','A','D','B','B']
Y = ['B','C','E','D','B','B']
LongestCommonSubstring(X, Y)

结果：

python，我又来啦~~~