欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最长公共子序列

程序员文章站 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('')