概念

什么是子串?
如下一个字符串


hello world!

其中hello是该字符串的子串,h也是该字符串的子串。如果一个字符串为空,我们称这个是一个空串
什么是公共子串?
如下两个字符串


str1 = 'hello world!'
str2 = 'hello! How are you doing?'

他们的公共子串有helloa等等,如果一个字符或字符串属于str1的同时又属于str1,那么这个字符或字符串是str1和str2的公共子串。
其中最长公共子串为:hello

思路

这里只记录一种思路:矩阵
有字符串s1和2,分别如下:


s1 = 'abcdefg'
s2 = 'defgcde'

s2的每一个字符去比对s1的字符,如果相同,对应s1字符索引值为1不同为0,于是有了下面这个矩阵

s1abcdefg
-x1x2x3x4x5x6x7
y10001000
y20000100
y30000010
y40000001
y50010000
y60001000
y70000100

可以看到,如果连续的子串相同将会产生一条斜线,这条斜线的长短就可以得出公共子串的长度,四个1连起来就是四个公共子串,于是优化以下:

s1abcdefg
-x1x2x3x4x5x6x7
y10001000
y20000200
y30000030
y40000004
y50010000
y60002000
y70000300

如果当前字符和上一个字符串相同,那么在索引位置处加上上一个索引位置的值

实现代码

def findit(str1, str2):
    """
    求两个字符串的最长公共子串
    :param str1: 字符串一
    :param str2: 字符串二
    :return: 最长公共子串
    """
    matrix = [[0] * len(str1) for i in range(len(str2))]
    # 初始化阵列表,一次性开辟空间
    xmax = 0
    xindex = 0

    for y, i in enumerate(str2):
        # y轴
        for x, j in enumerate(str1):
            # x轴
            if x == 0 or y == 0:
                # 如果 x,y轴处于边界状态,那么不需要加上层,否则超出边界
                # 相等直接等于1
                if i == j:
                    matrix[y][x] = 1
            else:
                if i == j:
                    matrix[y][x] = matrix[y - 1][x - 1] + 1

            if matrix[y][x] > xmax:
                xmax = matrix[y][x]
                xindex = x + 1
                # xindex = x
                # xindex += 1   # 切片后不包,所以需要+1
                # 记录阵列最大值及其索引

    return str1[xindex - xmax:xindex]


s1 = 'abcdefg'
s2 = 'defgcde'

print(findit(s1, s2))
Last modification:June 18th, 2020 at 03:55 pm
If you think my article is useful to you, please feel free to appreciate