一、代码
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'}
