问题标签 [lcs]

问题：需要两个字符串之间的 LCS 长度。字符串的大小最多为 100 个字符。字母表是通常的 DNA 之一，4 个字符“ACGT”。动态方法不够快。

我的问题是我正在处理很多对（据我所见，数量为数亿）。我相信我已将 LCS_length 函数的调用降至最低，因此使我的程序运行得更快的唯一另一种方法是使用更高效的 LCS_Length 函数。

我开始采用通常的动态编程方法。这给出了正确的答案，并有望正确实施。

那应该是 O(mn)（希望如此）。

然后为了寻找速度，我发现这篇文章Longest Common Subsequence 给出了Myers 的O(ND) 论文 。我尝试了将 LCS 与最短编辑脚本 (SES) 相关联的方法。他们给出的关系是 D = M + N - 2L，其中 D 是 SES 的长度，M 和 N 是两个字符串的长度，L 是 LCS 的长度。但这在我的实现中并不总是正确的。我给出了我的实现（我认为这是正确的）：

主要有例子。例如。“tomato”和“potato”（不要评论），LCS 长度为 4。实现发现它是 5，因为 SES（代码中的 D）出现为 2 而不是我期望的 4（删除“t”，插入“p”，删除“m”，插入“t”）。我倾向于认为 O(ND) 算法也可能计算替换，但我不确定这一点。

欢迎任何可实施的方法（我没有高超的编程技能）。（例如，如果有人知道如何利用小字母表）。

编辑：我认为最重要的是说，我在任何时候都在任何两个字符串之间使用 LCS 函数。因此，与其他几百万相比，它不仅是字符串说 s1。可能是 s200 和 s1000，然后是 s0 和 s10000，然后是 250 和 s100000。也不太可能跟踪最常用的字符串。我要求 LCS 长度不是近似值，因为我正在实现一个近似算法并且我不想添加额外的错误。

编辑：刚刚跑了callgrind。对于 10000 个字符串的输入，对于不同的字符串对，我似乎调用了 lcs 函数大约 50,000,000 次。（10000 个字符串是我想要运行的最低值，最大值是 100 万个（如果可行的话））。

[注意：我事先搜索过，找不到解决所有子序列的 LCS 问题的建议。]

我在编写“最长公共子序列”问题的解决方案时遇到了麻烦，我返回两个输入字符串的所有最长公共子序列。我查看了维基百科页面并尝试在那里实现伪代码，但我的“backtrackAll”方法遇到了问题。我相信我在下面正确计算了 LCS 矩阵，但我的“backtrackAll”方法返回一个空集。关于我做错了什么的任何提示？

有一种动态规划算法可以找到两个序列的最长公共子序列。如何找到两个序列 X 和 Y 的 LCS 算法。（正确性测试）

好的，这就是我想要做的：

获取两个以上的字符串并“对齐”它们（没有 DNA/RNA 序列等，只是常规字符串，每个字符串都不像 1000 个项目）

我已经完成了一些成对对齐（对齐两个字符串）的工作，但是当我尝试对齐多个字符串时，“间隙”给我带来了一些问题。

示例（我目前正在测试的一个）：

还有另一个（更具说明性的）示例：

我目前在做什么：

• 对字符串进行排序（较长的字符串在列表中排在第一位）
• 对齐第一对：AB 并得到结果（比方说R1）
• 然后对齐第二对：R1和C（结果R2）
• 然后对齐第三对：R2和D
• 等等...

那么你的想法是什么？我怎么能去呢？有没有更好的办法？（当然，必须有……）

我宁愿在 Perl/Python 或类似的东西中这样做，但是任何类型的代码/参考都会受到欢迎！:-)

我在网上搜索了一个 C++ Longest Common Substring 实现，但没有找到一个像样的。我需要一个返回子字符串本身的 LCS 算法，所以它不仅仅是 LCS。

不过，我想知道如何在多个字符串之间执行此操作。

我的想法是检查 2 个字符串之间最长的一个，然后检查所有其他字符串，但这是一个非常缓慢的过程，需要在内存中管理许多长字符串，这使得我的程序非常慢。

知道如何加快多个字符串的速度吗？谢谢你。

重要编辑 我给定的变量之一决定了最长公共子字符串需要包含的字符串数量，因此可以给我 10 个字符串，并找到它们的 LCS（K=10），或 4 个的 LCS他们，但我不知道哪个 4，我必须找到最好的 4。

因此，我在 C++ 中为算法介绍书 (CLRS) 实现了最长公共子序列算法，它工作得很好，有点。当我做这样的事情时：

./lcs abc bc > OUTPUT

当我在 中打开OUTPUT文件时vim，我看到：

2 bc^@

这是正确的，没有那个奇怪的^@符号。我做了一些谷歌搜索，这似乎是某种NULL角色？

我以前从未遇到过这个问题..有人知道如何摆脱它吗？

谢谢！-kstruct

编辑 这是执行打印的代码：

lcsString一个在哪里std::string。不确定这是否有帮助...

对于问题10635 uva，如何从最长公共子序列减少到 O(nlog n) 最长增加子序列。我需要一些有关解决问题的逻辑的帮助。

In order to find the minimal number of insertions required to convert a given string(s) to palindrome I find the longest common subsequence of the string(lcs_string) and its reverse. Therefore the number of insertions to be made is length(s) - length(lcs_string)

What method should be employed to find the equivalent palindrome string on knowing the number of insertions to be made?

For example :

1) azbzczdzez

Number of insertions required : 5 Palindrome string : azbzcezdzeczbza

Although multiple palindrome strings may exist for the same string but I want to find only one palindrome?

有人知道如何在 Ocaml 语言中找到一组字符串的最长公共子序列吗？

Rubydiff-lcs库在生成从一个序列到另一个序列所需的变更集方面做得很好，但是输出的格式让我有些困惑。我希望有一个更改列表，但输出始终是一个包含一个或两个更改列表的列表。拥有多个更改列表的含义/意图是什么？

考虑以下简单示例：

忽略最后一个更改是空白的事实，为什么有两个更改列表而不是一个？