我编写了这些函数(有效)来查找两个字符串的最长公共(public)子序列。
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
有没有人提议修改函数 s.t.他们可以打印三个字符串的最长公共(public)子序列吗？ IE。函数调用将是:lcs(str1, str2, str3)
到现在为止，我都是用“reduce”语句来管理它，但我想要一个函数，它可以在没有“reduce”语句的情况下真正打印出子序列。
请您参考如下方法:
要找到 D 个字符串的最长公共(public)子串，您不能简单地使用 reduce，因为 3 个字符串的最长公共(public)子串不一定是两个字符串的 LCS 的子串。反例:
a = "aaabb"
b = "aaajbb"
c = "cccbb"
在示例中，LCS(a,b) = "aaa"和 LCS(a, b, c) = "bb"。如您所见，“bb”不是“aaa”的子串。
在你的例子中，由于你实现了动态规划版本，你必须构建一个 D 维网格并相应地调整算法。
您可能想查看后缀树，这会使事情变得更快，请参阅 Wikipedia .也看看这个stackoverflow question
