一奸鸯、代碼
def lcstring(string1, string2):
len1 = len(string1)
len2 = len(string2)
# dp[i][j]表示string1和string2中，以string1[i]/string2[j]結(jié)尾的最長公共子串長度
# 當(dāng)i,j皆大于0時(shí)可帽，若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)]
# 用于保存當(dāng)前階段最長公共子串的長度
max_len = 0
# 用于保存長度為當(dāng)前階段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娄涩、運(yùn)行結(jié)果
5
{'asdfd', 'derty'}
