文章/答案/技术大牛

发布

社区首页 >问答首页 >两个字符串最长公共子序列的长度

问两个字符串最长公共子序列的长度
EN

Stack Overflow用户

提问于 2010-10-01 21:02:43

回答 2查看 1.7K关注 0票数 1

我试图编写一个函数来计算两个输入字符串str1和str2的最长公共子序列的长度。

这就是我现在的情况，

(define LCS
  (lambda (str1 str2)
    (if (OR (equal? str1 "") (equal? str2 ""))
        0
        (if (equal? (string-contains str1 (string-ref str2 0)) #t) 
            (+ 1 (LCS (substring str1 1 (string-length str1)) 
                      (substring str2 1 (string-length str2))))
            (LCS (substring str1 1 (string-length str1)) 
                 (substring str2 1 (string-length str2)))))))

其中，如果字符串中包含某个字符，string-contains将返回true。现在看来是可行的，但我想可能有个bug。

scheme

回答 2

Stack Overflow用户

回答已采纳

发布于 2010-10-01 21:43:21

如果您不介意一个相对较慢的算法，那么您的代码就完全在正确的轨道上了；如果您需要使用更快的动态编程，那么有一种更复杂的方法来解决这个问题。

现在，您的代码中的错误是，在每次递归调用的同时，您正在向下移动两个字符串的长度。例如，它将失败(我想，我还没有试过)使用以下两个字符串：(LCS "scheme" "emesch")的原因是匹配的子字符串在第一个字符串和第二个字符串中的位置不相同。

我建议将递归分解为两个递归调用:一个从第一个字符串的前面删除一个字符，另一个从第二个字符串的前面删除一个字符。然后，你会从这两个电话中得到最好的结果。以这种方式，您可以确保无论子字符串位于另一个字符串中，都会找到子字符串。

票数 2

Stack Overflow用户

发布于 2012-06-21 17:20:10

这两个字符串并行扫描。如果当前两个字符相同，最长公共子序列的长度将增加一个，并且扫描将在每个字符串中的下一个字符处继续进行；否则，在从一个输入序列或另一个输入序列中删除当前字符之后，递归地考虑两种可能性，最长公共子序列的长度就是这两种可能性中最大的一种。

我的博客提供了更完整的解释和方案中的实现。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/3843038

复制

相似问题

问两个字符串最长公共子序列的长度
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问两个字符串最长公共子序列的长度EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问两个字符串最长公共子序列的长度
EN