python解决最长公共子串和最长公共子序列

小半 • 2023年1月13日下午2:19 • 技术随笔 • 阅读 380

什么是最长公共子串？？🤔
最长公共子串就是指两个字符串中有部分子串相同且是最长的那个，例如，“abcdef” 和 “fgbcda” 的最长公共子串就是 “bcd”。

什么是最长公共子序列？？🤔
先来了解一下是什么是子序列，在数学应用中，某个序列的子序列就是从最初的序列通过去除某些元素但不破坏余下元素的相对位置(在前或者在后) 而形成的新序列。假设序列 “abcde” ,如果找到一个子序列可以是 “abc”、“ace”、或 “be”，但不可以是 “cae”。所以说如果求列表A和列表B的最长公共子序列，就是说既是A的额子序列又是B的子序列，而且要保证最长。

这两个问题都可以用二维的列表来解决

一、求最长公共子串长度

分别将两个要处理的字符串进行行和列上的二维化，把两两字母的比较结果映射到二维列表中。画出如下表格，分别对每个字母进行比较，处理方法如下图中所示：

str_a = 'hish'
str_b = 'fish'
cell = [[0 for j in range(len(str_a)+1)] for i in range(len(str_b)+1)]
#print(cell)
for j in range(1,len(str_a)+1):
    for i in range(1,len(str_b)+1):
        if str_a[j-1]==str_b[i-1]:
            cell[i][j] = cell[i-1][j-1]+1
        # else:
        #     cell[i][j] = 0
#print(cell)
maxList = []
for li in cell:
    maxList.append(max(li))
print(max(maxList))

二、求最长公共子序列长度

处理方式和上面类似，也是采用二维列表实现。

str_a = 'fosh'
str_b = 'fish'
cell = [[0 for j in range(len(str_a)+1)] for i in range(len(str_b)+1)]

for j in range(1,len(str_a)+1):
    for i in range(1,len(str_b)+1):
        if str_a[j-1]==str_b[i-1]:
            cell[i][j] = cell[i-1][j-1]+1
        else:
            cell[i][j] = max(cell[i-1][j],cell[i][j-1])
max_List = []
for li in cell:
    max_List.append(max(li))
print(max(max_List))