介绍
子串和子序列的意思不一样，如下图所示，子序列不要求连续，只需要在给定序列中出现过，并且相对顺序一致。而子串需要连续。
图片来自动态规划 最长公共子序列 过程图解
最长公共子串：
同时出现在两个字符串中的最长子串
实现
使用动态规划的方法，思想如下：
对于两个字符串 x x x与 y y y
d p [ i , j ] dp[i, j] dp[i,j]表示公共子串的最大长度，该公共子串以 x x x的第 i i i个字符结尾并且以 y y y的第 j j j个字符结尾
完成所有 d p dp dp的计算后，选择最大的dp值，即为两个字符串 x x x与 y y y的最长公共子串长度；
往前回溯，即可得到最长公共子串
从上面的思想可知，如果 x x x的第 i i i个字符结与 y y y的第 j j j个字符不相等，则 d p [ i , j ] = 0 dp[i, j]=0 dp[i,j]=0，因为公共子串不可能以两个不同的字符结尾。
递推公式如下：
d p [ i , j ] = { 0 若 i = 0 或 j = 0 d p [ i − 1 , j − 1 ] + 1 若 i , j ≥ 0 , x i − 1 = y j − 1 0 若 i , j ≥ 0 , x i − 1 ≠ y j − 1 dp[i, j]= \begin{cases}0 & \text { 若 } i=0 \text { 或 } j=0 \\ dp[i-1, j-1]+1 & \text { 若 } i, j\geq0, x_{i-1}=y_{j-1} \\ 0& \text { 若 } i, j\geq0, x_{i-1} \neq y_{j-1}\end{cases} dp[i,j]=⎩⎪⎨⎪⎧0dp[i−1,j−1]+10 若 i=0 或 j=0 若 i,j≥0,xi−1=yj−1 若 i,j≥0,xi−1=yj−1
代码如下：
def longestCommonSubstr(self, word1: str, word2: str) -> int:m = len(word1)n = len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]# dp[i][j]代表word1以i结尾,word2以j结尾，的最大公共子串的长度max_len = 0row = 0col = 0for i in range(1, m + 1):for j in range(1, n + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1if max_len < dp[i][j]:max_len = dp[i][j]row = icol = jmax_str = ""i = rowj = colwhile i > 0 and j > 0:if dp[i][j] == 0:breaki -= 1j -= 1max_str += word1[i]lcstr = max_str[::-1]# 回溯的得到的最长公共子串print(lcstr)return max_len
obj = Solution()
word1 = "caba"
word2 = "abc"
res = obj.longestCommonSubstr(word1, word2)
print(res)
# 2, 子串为ab
dp矩阵的值：
从最长公共子串位置，向前回溯，直到dp对应的值为0，得到最大公共子串的结果
