【python】求两个字符串的公共字串？

题目：找出两个字符串的最长公共字串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。

分析：动态规划法。通过把中间的比较结果记录下来，从而可以避免字符的重复比较。：

首先定义二元函数（i，j）：表示分别以s1[i],s2[j]结尾的公共子串的长度，显然，f（0， j） = 0 (j >= 0),f(i, 0) = 0(i >= 0),那么对于f(i +1, j + 1)而言，则有如下两种取值：
（1) f(i + 1, j +1) = 0,当str1[i + 1] != str2[j + 1]时

（2）f(i + 1, j +1) = f(i, j) + 1,当str1[i + 1] == str2[j + 1]时

根据这个公式可以计算出f(i, j)（0<= i<=len(s1), 0 <= j <= len(s2)，所有的值，从而可以找出最长的子串。

def getMaxSubStr(str1, str2):

    len1 = len(str1)

    len2 = len(str2)

    sb = ''

    maxs = 0  # 用来记录最长公共子串的长度

    maxI = 0  # 用来记录最长公共字串最后一个字符的位置

    # 申请新的空间来记录公共字串长度信息

    M = [([None] * (len1 + 1)) for i in range(len2 + 1)]

    i = 0

    while i < len1 + 1:

        M[i][0] = 0

        i += 1

    j = 0

    while j < len2 + 1:

        M[0][j] = 0

        j += 1

    # 通过利用递归公式填写新建得二维数组（公共字串得长度信息）

    i = 1

    while i < len1 + 1:

        j = 1

        while j < len2 + 1:

            if list(str1)[i - 1] == list(str2)[j - 1]:

                M[i][j] = M[i - 1][j - 1] + 1

                if M[i][j] > maxs:

                    maxs = M[i][j]

                    maxI = i

            else:

                M[i][j] = 0

            j += 1

        i += 1

    i = maxI - maxs

    while i < maxI:

        sb = sb + list(str1)[i]

        i += 1

    return sb

if __name__ == "__main__":

    str1 = 'abccade'

    str2 = 'dgcadde'

    print(getMaxSubStr(str1, str2))

程序运行结果：

cad