[Python]获取2个字符串的最长公共子串

- @[toc]1.问题引出源码及测试结果2.1. 程序源码2.2. 测试结果分析Next

def getMaxCommonSubstr(s1, s2):
# 求两个字符串的最长公共子串
# 思想：建立一个二维数组，保存连续位相同与否的状态

    len_s1 = len(s1)
    len_s2 = len(s2)

    # 生成0矩阵，为方便后续计算，多加了1行1列
    # 行: (len_s1+1)
    # 列: (len_s2+1)
    record = [[0 for i in range(len_s2+1)] for j in range(len_s1+1)]    
    
    maxNum = 0          # 最长匹配长度
    p = 0               # 字符串匹配的终止下标 

    for i in range(len_s1):
        for j in range(len_s2):
            if s1[i] == s2[j]:
                # 相同则累加
                record[i+1][j+1] = record[i][j] + 1
                
                if record[i+1][j+1] > maxNum:
                    maxNum = record[i+1][j+1]
                    p = i # 匹配到下标i

    # 返回 子串长度，子串
    return maxNum, s1[p+1-maxNum : p+1]



def printMatrixList(li):
# 打印多维list
    row = len(li)
    col = len(li[0])
    
    for i in range(row):
        for j in range(col):
            print(li[i][j], end=' ')
        print('')


    
    
if __name__ == "__main__":

    # s1="黑猫英语名著3级 02 Alic's Adventures In Wonderland 艾丽丝漫游奇境记.pdf"
    # s2="艾丽丝漫游奇境记 Alic_s Adventures In Wonderland 01.mp3"
    s1='abcdef'
    s2='bcxdef'
    [lenMatch,strMatch] = getMaxCommonSubstr(s1,s2)
    print('子串: ', strMatch)
    print('子串长度: ', lenMatch)

# 如果数据是`abcdef`等
子串:  def
子串长度:  3

# 如果数据是`艾丽丝`等
子串:  s Adventures In Wonderland
子串长度:  27

s1='abcdef'
s2='bcxdef'

0 b c x d e f
a 0 0 0 0 0 0
b 1 0 0 0 0 0
c 0 2 0 0 0 0
d 0 0 0 1 0 0
e 0 0 0 0 2 0
f 0 0 0 0 0 3