Loading... ##概念 **什么是子串？** 如下一个字符串 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 日 03 : 55 PM © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付
