python求两个字符串的最长子串

2020 年 06 月 18 日

820 次浏览

2191字数

##概念
**什么是子串？**
如下一个字符串
    
    hello world!

其中`hello`是该字符串的子串，`h`也是该字符串的子串。如果一个字符串为空，我们称这个是一个`空串`。
**什么是公共子串？**
如下两个字符串
    
    str1 = 'hello world!'
    str2 = 'hello! How are you doing?'

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

##思路
这里只记录一种思路：**矩阵**
有字符串`s1`和`和2`，分别如下：
    
    s1 = 'abcdefg'
    s2 = 'defgcde'

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

|s1|a|b|c|d|e|f|g|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|-|x1|x2|x3|x4|x5|x6|x7|
|y1|0|0|0|**1**|0|0|0|
|y2|0|0|0|0|**1**|0|0|
|y3|0|0|0|0|0|**1**|0|
|y4|0|0|0|0|0|0|**1**|
|y5|0|0|**1**|0|0|0|0|
|y6|0|0|0|**1**|0|0|0|
|y7|0|0|0|0|**1**|0|0|

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

|s1|a|b|c|d|e|f|g|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|-|x1|x2|x3|x4|x5|x6|x7|
|y1|0|0|0|**1**|0|0|0|
|y2|0|0|0|0|**2**|0|0|
|y3|0|0|0|0|0|**3**|0|
|y4|0|0|0|0|0|0|**4**|
|y5|0|0|**1**|0|0|0|0|
|y6|0|0|0|**2**|0|0|0|
|y7|0|0|0|0|**3**|0|0|

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

##实现代码

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))

最后修改：2020 年 06 月 18 日