python【数据结构与算法】最长公共子串详解（附代码）

1 定义

和最长公共子序列一样，使用动态规划的算法。
下一步就要找到状态之间的转换方程。

和LCS问题唯一不同的地方在于当A[i] != B[j]时，res[i][j]就直接等于0了，因为子串必须连续，
且res[i][j] 表示的是以A[i]，B[j]截尾的公共子串的长度。
因此可以根据这个方程来进行填表，以"helloworld"和“loop”为例：

def LCstring(string1,string2):
    len1 = len(string1)
    len2 = len(string2)
    res = [[0 for i in range(len1+1)] for j in range(len2+1)]
    result = 0
    for i in range(1,len2+1):
        for j in range(1,len1+1):
            if string2[i-1] == string1[j-1]:
                res[i][j] = res[i-1][j-1]+1
                result = max(result,res[i][j])  
    return result
print(LCstring("helloworld","loop"))