查找字符串最长公共子串

有些偷懒的方法

while 1:
    try:
        a, b = input().split()
        if len(a) < len(b):
            a, b = b, a
        n = 0
        l = []
        for i in range(len(a)):
            if a[i-n:i+1] in b:
                n += 1
        for i in range(len(a)-n+1):
            if a[i:i+n] in b:
                l.append(a[i:i+n])
        for i in sorted(l):
            print(i)
    except:
        break

用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0。然后求出对角线最长的1的序列，其对应的位置就是最长匹配子串的位置。

def find_lcsubstr(s1, s2):
    res = [] # 存储所有匹配的子串
    m = [[0 for i in range(len(s2)+1)]
         for j in range(len(s1)+1)]  # 生成0矩阵，为方便后续计算，比字符串长度多了一列
    mmax = 0  # 最长匹配的长度
    p = 0  # 最长匹配对应在s1中的最后一位
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                m[i+1][j+1] = m[i][j]+1
                if m[i+1][j+1] > mmax:
                    res = []
                    mmax = m[i+1][j+1]
                    p = i+1
                    res.append(s1[p-mmax:p])
                elif m[i+1][j+1] == mmax:
                    p = i+1
                    res.append(s1[p-mmax:p])
    return res  # 返回结果


s1, s2 = input().split()
for i in sorted(find_lcsubstr(s1, s2)):
    print(i)