区别最长公共子串（连续）
'''
LCS 最长公共子序列
''' def LCS_len(x, y):
m = len(x)
n = len(y)
dp = [[0] * (n + 1) for i in range(m + 1)]
B = [[' '] * (n + 1) for i in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
B[i][j] = 'X'
elif dp[i - 1][j] > dp[i][j - 1]:
dp[i][j] = dp[i - 1][j]
B[i][j] = 'L'
else:
dp[i][j] = dp[i][j - 1]
B[i][j] = 'T'
print(dp)
return dp, B def LCS_str(B, x, i, j):
if i == 0 or j == 0:
return
if B[i][j] == 'X':
print(x[i - 1])
LCS_str(B, x, i - 1, j - 1) elif B[i][j] == 'L':
LCS_str(B, x, i - 1, j)
else:
LCS_str(B, x, i, j - 1) def main():
x = 'ABDC'
y = 'AFBC'
dp, B = LCS_len(x, y)
LCS_str(B, x, len(x), len(y))
main()