最长公共子序列
程序员文章站
2024-03-17 21:52:40
...
如果字符串1的所有字符按照在字符中的顺序出现在另外一个字符串2中,则字符串1称之为字符串2 的子串。注意,并不是要求子串(字符串1)的字符必须连续出现在字符串2中。
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长的公共子串。例如,输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是他们的最长公共子串,则输出他们的长度为4,并打印任意一个子串。
def lcs(a, b):
lena = len(a)
lenb = len(b)
c = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
flag = [[0 for i in range(lenb + 1)] for j in range(lena + 1)]
for i in range(lena):
for j in range(lenb):
if a[i] == b[j]:
c[i + 1][j + 1] = c[i][j] + 1
flag[i + 1][j + 1] = 'ok'
elif c[i + 1][j] > c[i][j + 1]:
c[i + 1][j + 1] = c[i + 1][j]
flag[i + 1][j + 1] = 'left'
else:
c[i + 1][j + 1] = c[i][j + 1]
flag[i + 1][j + 1] = 'up'
return c, flag
def printLcs(flag, a, i, j):#打印公共子串
if i == 0 or j == 0:
return
if flag[i][j] == 'ok':
printLcs(flag, a, i - 1, j - 1)
print(a[i - 1], end='')
elif flag[i][j] == 'left':
printLcs(flag, a, i, j - 1)
else:
printLcs(flag, a, i - 1, j)
a = 'ABCBDAB'
b = 'BDCABA'
c, flag = lcs(a, b)
for i in c:
print(i)
print('')
for j in flag:
print(j)
print('')
printLcs(flag, a, len(a), len(b))
print('')