问题标签 [lcs]

我正在尝试编写一个递归算法来查找两个列表的最长公共子序列，如http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined中所述

似乎递归永远不会结束，我无法弄清楚我在做什么错

任何解决此问题的帮助表示赞赏。谢谢你。

我有一个包含 2 列的表，一个是 id，另一个是包含长字符串的列，例如。

当用户执行搜索时，我会在搜索字符串中找到最长的公共子序列以及表中的所有数据。例如。搜索顺序是

TCTGTTCTG

有没有办法存储关于匹配的信息，它从哪里开始找到匹配，然后到哪里找到匹配，然后又从哪里开始等等？所以，我可以用这种格式来表示数据

基本上我可以以某种方式存储每个找到的子序列的每个序列的开始和结束位置，这样当我以后再次显示这个页面时，我不必再次计算这个匹配，并且可以以某种方式挑选出关于开始和的数据从数据库结束并以所示格式显示？我知道这个问题可能有点模糊，但是如果您有任何疑问，请告诉我我还能如何详细说明？

嗨，这是我的 c# 中 2 个字符串的最长公共子序列的代码。我需要帮助回溯。我需要找出子序列：GTCGT

给定一个像 . 这样的字符串，"geekthegeertheregeers"所以我们必须在字符串本身中找到最长的公共子字符串。

就像在这种情况下"geer"将是最长的公共子字符串。我的问题是这里将应用哪种算法。可以修改 LCS 以找到此问题的解决方案吗？

我有 2 个序列，需要找到最长的公共子序列。无法弄清楚为什么我的功能恢复不起作用。

如果我做

函数返回

我认为，这个问题出在索引中，但找不到它在哪里。

上周我一直在研究 LCS 问题，我有一个问题。

每当我们也对找到最长的子序列本身（而不仅仅是它的长度）感兴趣时，我们创建一个辅助 (string1.length X string2.length) 矩阵，通过添加向上箭头、向左箭头或对角箭头来确定子序列是什么，对应于我们来自哪里，因此我们可以稍后回溯我们的步骤并找到子序列本身。

（参见此处的示例：http: //www.columbia.edu/~cs2035/courses/csor4231.F13/lcs.pdf在最后一页）

我的问题是：考虑以下输出矩阵来运行这两个字符串：“abfcytyruc”和“vxczcxabfc”通过 LCS：

我们真的可以仅根据矩阵中的最后一列找到公共子序列，而不需要更多的空间复杂度吗？

我刚刚完成了一个程序，它可以分别报告所有可能的 LCS 和两个字符串的位置。但是，测试用例的输出并不完全正确。

例如，如果这两个字符串是“ACADABCDADCB”和“DCACDCBBDBAD”，那么正确的结果应该报告 8 个案例。我的输出只报告了 6 个案例，如下所示：

--- 输出 --- 最大。长度 = 7
LCS：ACDBDAD，在 X：2 3 5 6 8 9 10，在 Y：3 4 5 7 9 11 12
LCS：ACDBDAD，在 X：2 3 5 6 8 9 10，在 Y：3 4 5 8 9 11 12
LCS：ACDCDAD，在 X：2 3 5 7 8 9 10，在 Y：3 4 5 6 9 11 12
LCS：CADBDAD，在 X：3 4 5 6 8 9 10，在 Y：2 3 5 7 9 11 12
LCS：CADBDAD，在 X：3 4 5 6 8 9 10，在 Y：2 3 5 8 9 11 12
LCS：CADCDAD，在 X：3 4 5 7 8 9 10，在 Y：2 3 5 6 9 11 12

请给我一些建议。非常感谢！

我试图在多个序列中找到最长的公共子串（LCS）。

CPAN 上有许多模块实现了 2 个序列的 LCS 算法，例如算法::Diff和 String::LCSS_XS，但我很难将它们扩展为使用超过 2 个序列，因为跨多个序列的 LCS 不一定是它们中的任何两个之间的 LCS。

值得注意的是，尽管它的名称，Algorith::MLCS实际上并不返回 LCS，而是返回许多数组的所有公共元素（也是非连续的）。我的印象是它被设计破坏了，但我可能错了。

Algorithm::Diff和A​​lgorith::MLCS解决最长公共子序列问题，而不是最长公共子串问题。

有没有明显的方法来扩展 n=2 算法或者我必须实现我的版本？如果是，如何？

谢谢。

在Common Child的编程挑战中，我采用了与一般最长公共子串问题不同的方法。该代码是

采用较小的测试用例我能够获得解决方案，但我无法获得更长的解决方案。

我所做的是

输入：ABCDEF - 设为 FBDAMN - 设为 b，因为它已插入代码中。输出：2。即。因为 BD 是子字符串。

所以我在这里做的是检查a的每个子字符串的可匹配子字符串，并打印最大的。IE。ABCDEF, BCDEF,CDEF,DEF,EF,F 的子字符串，表示此处的最外层循环。（循环 i）

现在第二个循环匹配字符串中的每个字母，即。它迭代 (1...n),(2...n),(3...n),...,(n)，这意味着它从 i 指定的字母开始。

现在第三个循环遍历整个字符串 B 以查看 a[j] 是否与 B 中的任何字母匹配，如果是，则 count 递增。

由于我们只能从子字符串中删除字母而不是弄乱它，即每个字母在两个字符串中应该具有相同的相对顺序，因此我在找到前一个字母后使用 x 搜索 B。

试运行就像示例（从 0 到 n-1 的数组）

a= abcdef b= fbdamn

当 i=0 - 整个字符串匹配 abcdef

x=-1 所以 k 从 0 迭代到 n-1 所以，a=f？a=b？a=d? 一个=一个？计数=计数+1；所以x设置为3（a的位置）。A 中的 a 之后的元素只能出现在 B 中的 a 之后，因此 x=3。因此 k 从 4 迭代到 5 b=m？b=n? c=m?c=n? ………………

现在我们保存先前计数的值，如果它大于之前的计数。所以 maxcount=count 然后将 count 重置为 0，并重置位置 x=-1。

i=1 即字符串 = BCDEF k 从 0 到 n 所以，B=F？b=b？count=count+1 // 变为 1 x 设置为 1(B 的位置) k 从 2 到 nc=d? c=a?c=m?c=n? k 从 2 到 nd=d？count = count+1 // 变为 2 x 设置为 2 k 从 3 到 ne=a?e=m?e=n? k 从 3 到 nf=a?f=m?f=n? 然后如果最大计数（代码中的prev）大于当前计数，则maxcount = count，重置count = 0，x = -1；然后对于 CDEF,DEF,EF,F 就这样了，这里的最大子字符串变成了 2

适用于较短的测试用例，但不适用于较长的测试用例。

它适用的测试用例是：

OUDFRMYMAW AWHYFCCMQX

带输出 2

不适合

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

正确的输出是15，我的输出是10。任何人都可以向我解释我在哪里犯了错误

请帮助我尝试找到我实现最大常见子字符串问题的运行时间

函数 std::find 需要 O(n) 时间。所以这应该是 O(nm) 其中 n 和 m 是字符串的长度。是否超过 O(nm) ？