求两个字符串的最长公共子串

参考：https://blog.csdn.net/qq_25800311/article/details/81607168

问题：有两个字符串str1和str2，求出两个字符串中最长公共子串长度。

比如：str=acbcbcef，str2=abcbced，则str1和str2`的最长公共子串为bcbce，最长公共子串长度为5。

算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
针对于上面的两个字符串我们可以得到的二维矩阵如下：

最大公共字符串_1.jpg

从上图可以看到，str1和str2共有5个公共子串，但最长的公共子串长度为5。

为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：

最大公共字符串_2.jpg

根据作者的C++代码转换为Python，代码如下：

import numpy as np
def getLCS(str1, str2):
    record = np.zeros((len(str1), len(str2)))
    maxLen, maxEnd = 0, 0
    for i in range(0, len(str1)):
        for j in range(0, len(str2)):
            if str1[i] == str2[j]:
                if i == 0 or j == 0:
                    record[i][j] = 1
                else:
                    record[i][j] = record[i - 1][j - 1] + 1
            else:
                record[i][j] = 0
            
            if record[i][j] > maxLen:
                maxLen = record[i][j]
                maxEnd = i 
    return (record,maxEnd,maxLen)

mtx, end, maxlen = getLCS('abcbced','acbcbcef')
print(mtx)

[[1. 0. 0. 0. 0. 0. 0. 0.]
[0. 0. 1. 0. 1. 0. 0. 0.]
[0. 1. 0. 2. 0. 2. 0. 0.]
[0. 0. 2. 0. 3. 0. 0. 0.]
[0. 1. 0. 3. 0. 4. 0. 0.]
[0. 0. 0. 0. 0. 0. 5. 0.]
[0. 0. 0. 0. 0. 0. 0. 0.]]

获取公共字符串为：
[int(end - maxlen + 1):int(end)+1]
获取最长度为：
maxlen