给定两个字符串
S
1
，
S
2
S_1 ， S_2
S1，S2，找到一个最长的字符串
S
3
S_3
S3，要求
S
3
S_3
S3即是
S
1
S_1
S1的子串，又是
S
2
S_2
S2的子串
什么是子串：在字符串"12345"中，"123"是子串，“135”不是子串（是子序列）
设立二维矩阵max_tail_len[i][j]表示
S
1
S_1
S1以i为结尾，
S
2
S_2
S2以j为结尾的最长公共子序列长度，矩阵满足如下关系：
m
a
x
_
t
a
i
l
_
l
e
n
[
i
]
[
j
]
=
{
m
a
x
_
t
a
i
l
_
l
e
n
[
i
−
1
]
[
j
−
1
]
+
1
S
1
[
i
]
=
S
2
[
j
]
0
S
1
[
i
]
!
=
S
2
[
j
]
max_tail_len[i][j]=left{begin{array}{l}max_tail_lenlbrack i-1rbracklbrack j-1rbrack+1;;;S_1lbrack irbrack=S_2lbrack jrbrack\0;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;S_1lbrack irbrack;!=S_2lbrack jrbrackend{array}right.
max_tail_len[i][j]={max_tail_len[i−1][j−1]+1S1[i]=S2[j]0S1[i]!=S2[j]
根据此关系即从低索引到高索引更新出矩阵的值，代码如下（代码中的res表示公式中的max_tail_len[i][j]）：
res = [[0]*len(str2) for _ in range(len(str1))]
for i in range(len(str1)):
for j in range(len(str2)):
if str1[i]==str2[j]:
if i>0 and j>0:
res[i][j]=1+res[i-1][j-1]
else:
res[i][j]=1
之后在迭代期间保存最大的长度和字符串即可，整个代码如下：
def max_sub_str(str1,str2):
"""
最长公共字串
动态规划
时间复杂度O(n^2)
:param str1:
:param str2:
:return: 最大长度，最大长度子串列表
"""
res = [[0]*len(str2) for _ in range(len(str1))]
max_len=0
max_str=[]
for i in range(len(str1)):
for j in range(len(str2)):
if str1[i]==str2[j]:
if i>0 and j>0:
res[i][j]=1+res[i-1][j-1]
else:
res[i][j]=1
# 记录最大值
if res[i][j]>max_len:
max_len=res[i][j]
max_str=[str1[i-max_len+1:i+1]]
elif res[i][j]==max_len:
max_str.append(str1[i-max_len:i])
return max_len,max_str
复杂度
时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
