概念
什么是子串?
如下一个字符串
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))