1

我编写了这些函数（它们可以工作）来查找两个字符串的最长公共子序列。

def lcs_grid(xs, ys):
    grid = defaultdict(lambda: defaultdict(lambda: (0,"")))
    for i,x in enumerate(xs):
        for j,y in enumerate(ys):
            if x == y:
                grid[i][j] = (grid[i-1][j-1][0]+1,'\\')
            else:
                if grid[i-1][j][0] > grid[i][j-1][0]:
                    grid[i][j] = (grid[i-1][j][0],'<')
                else:
                    grid[i][j] = (grid[i][j-1][0],'^')

    return grid

def lcs(xs,ys):
    grid = lcs_grid(xs,ys)
    i, j = len(xs) - 1, len(ys) - 1

    best = []
    length,move = grid[i][j]
    while length:
        if move == '\\':
            best.append(xs[i])
            i -= 1
            j -= 1
        elif move == '^':
            j -= 1
        elif move == '<':
            i -= 1
        length,move = grid[i][j]

    best.reverse()
    return best

有没有人提议修改函数 st 他们可以打印三个字符串的最长公共子序列？即函数调用将是：lcs(str1, str2, str3)

到目前为止，我使用“reduce”语句来管理它，但我希望有一个函数可以在没有“reduce”语句的情况下真正打印出子序列。

4

1 回答 1

6

要找到 D 字符串的最长公共子串，您不能简单地使用reduce，因为 3 个字符串的最长公共子串不必是两者中任何一个的 LCS 的子串。反例：

a = "aaabb"
b = "aaajbb"
c = "cccbb"

在示例中，LCS(a,b) = "aaa" 和 LCS(a, b, c) = "bb"。如您所见，“bb”不是“aaa”的子字符串。

在您的情况下，由于您实现了动态编程版本，因此您必须构建一个 D 维网格并相应地调整算法。

您可能想查看后缀树，这应该会使事情变得更快，请参阅Wikipedia。也看看这个stackoverflow问题

于 2012-05-24T23:00:45.937 回答