一、代碼

def lcstring(string1, string2):
    len1 = len(string1)
    len2 = len(string2)
    # dp[i][j]表示string1和string2中，以string1[i]/string2[j]結尾的最長公共子串長度
    # 當i,j皆大于0時，若string1[i - 1] 與 string2[j - 1] 相等
    # 則 dp[i][j] = dp[i - 1][j - 1] + 1
    # 否則 dp[i][j] = 0
    dp = [[0 for j in range(len2 + 1)] for i in range(len1 + 1)]
    # 用于保存當前階段最長公共子串的長度
    max_len = 0
    # 用于保存長度為當前階段max_len的所有公共子串
    lcstring_set = None
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if string1[i - 1] == string2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    lcstring_set = set()
                    lcstring_set.add(string1[i - max_len:i])
                elif dp[i][j] == max_len:
                    lcstring_set.add(string1[i - max_len:i])
            else:
                dp[i][j] = 0

    return max_len, lcstring_set


max_len, lcstring_set = lcstring('habcdelloworldertyasdfd', 'loopabcdddqasdfdertyzsdfsv')
print(max_len)
print(lcstring_set)

2、運行結果

5
{'asdfd', 'derty'}