python解決最長公共子串和最長公共子序列

• 什麼是最長公共子串？？🤔

  最長公共子串就是指兩個字元串中有部分子串相同且是最長的那個，例如，“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))