如何找到指数时间最长的公共子序列? [英] How to find the Longest Common Subsequence in Exponential time?

问题描述

我可以使用动态编程以正确的方式做到这一点，但我不知道如何在指数时间内完成.

I can do this the proper way using dynamic programming but I can't figure out how to do it in exponential time.

我正在寻找两个字符串之间最大的公共子序列. 注意:我的意思是子序列而不是子字符串，组成序列的符号不必是连续的.

I'm looking to find the largest common sub-sequence between two strings. Note: I mean subsequences and not sub-strings the symbols that make up a sequence need not be consecutive.

推荐答案

只需用递归调用替换动态编程代码中表中的查找.换句话说，只需实施 LCS 问题的递归公式即可:

Just replace the lookups in the table in your dynamic programming code with recursive calls. In other words, just implement the recursive formulation of the LCS problem:

编辑

使用伪代码(实际上是python):

In pseudocode (almost-python, actually):

def lcs(s1, s2):
 if len(s1)==0 or len(s2)==0: return 0
 if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:])
 return max(lcs(s1, s2[1:]), lcs(s1[1:], s2))

这篇关于如何找到指数时间最长的公共子序列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！