javascript - 递归最长公共(public)子序列循环还是永远持续？

Question

我正在开发一个 JavaScript 应用程序，我需要一个最长公共(public)子序列的递归算法，所以我去了 here并尝试了这个。 事情是这样的:

function lcs(a, b) {
  var aSub = a.substr(0, a.length - 1);
  var bSub = b.substr(0, b.length - 1);

  if (a.length === 0 || b.length === 0) {
    return '';
  } else if (a.charAt(a.length - 1) === b.charAt(b.length - 1)) {
    return lcs(aSub, bSub) + a.charAt(a.length - 1);
  } else {
    var x = lcs(a, bSub);
    var y = lcs(aSub, b);
    return (x.length > y.length) ? x : y;
  }
}

它在我到目前为止尝试过的几个测试用例中运行良好，但我发现它在以下测试用例上循环:

a:该实体工作正常

b:这不能正常工作，但应该可以正常工作

它还循环使用:

a:该实体工作正常

b:这效果不太好

在某个时候应该进入中间分支。

我注意到它是同一算法的 Java 版本 ( here ) 的翻译。事情是这样的:

public static String lcs(String a, String b){
    int aLen = a.length();
    int bLen = b.length();
    if(aLen == 0 || bLen == 0){
        return "";
    }else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
        return lcs(a.substring(0,aLen-1),b.substring(0,bLen-1))
            + a.charAt(aLen-1);
    }else{
        String x = lcs(a, b.substring(0,bLen-1));
        String y = lcs(a.substring(0,aLen-1), b);
        return (x.length() > y.length()) ? x : y;
    }
}

假设 String.substr() 和 String.substring() 相同(但事实并非如此)，我认为 JavaScript 翻译是错误的。 为了确保情况并非如此，我在同一个测试用例上尝试了 Java here 。

你猜怎么着？ java版本也没有结束。

我正在努力调试它，因为它是递归的。 有人知道它出了什么问题吗？

Answer 1

正如其他人在评论中指出的那样，程序本身是正确的。您遇到的问题是由于在此实现中，代码的时间复杂度呈指数级，因此需要很长时间才能运行示例输入。如果你让它运行很长时间，它会返回正确的结果。

正如其他人在评论中指出的那样，两个字符串之间的 LCS 可以使用动态编程以较低的时间复杂度来解决，这将更快地解决它。请参阅互联网以获取更多帮助( wikipedia )，或者更好的是，尝试自己解决这个问题，考虑这样一个事实:对于每个长度为 n 的字符串，恰好有 N^2 个子字符串。您可以通过检查 b 中是否存在 a 的任何子字符串来简单地用 N^2*M^2(n m 是两个字符串的长度)来解决它。问问自己是否可以通过锻炼做得更好？如果是，如何，如果否，为什么。