高效的最长公共子序列算法库？

Question

我正在寻找一种在C++程序中使用的LCS算法实现，需要具有高效的空间利用率。输入是两个整数随机访问序列。
我目前正在使用维基百科关于LCS的动态规划算法实现。然而，这种方法的时间和内存都是O(mn)，对于较大的输入数据容易出现内存错误。
我了解到Hirschberg算法、Hunt-Szymanski算法和Masek与Paterson算法可以显著地提高内存利用率。但由于它们不是很容易实现，我更愿意在现有实现中尝试这些算法。请问是否有这样的库？我想既然文本差异工具非常普遍，应该会有一些开源库吧？

- BuschnicK

---

你对最长公共子序列本身感兴趣还是只对它的长度感兴趣？ - IVlad

有些失望的是，几次快速的网络搜索并没有找到什么特别有用的东西（在C语言中有很多char的临时实现，但没有任何基于Hirschberg线性空间加速或基于元素类型模板化的C++实现）。如果你找到了（或者自己创造了:D）任何东西，请更新！ - j_random_hacker

此外：虽然不是直接相关的话题，但Myers有几个O(nd)算法，其中d是所需编辑次数。非常适用于您预期相似的输入！（我认为其中一个仍在大多数“diff”中使用。） - j_random_hacker

到目前为止，我发现最好的是http://wordaligned.org/articles/longest-common-subsequence。不过，需要小心：C++版本在执行递归调用时会将迭代器增加到末尾之后。需要修复。此外，它没有实现公共前缀/后缀优化。 - BuschnicK

Answer 1

在搜索这些内容时，可以尝试使用scholar.google.com。它更适合查找学术作品。它找到了这篇文献：一个“最长公共子序列算法概述”的调查报告，链接如下：

http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf

- cadolphs

---

因为楼主想要算法的库实现，而不是仅仅描述，所以勉强给予一个+1。但这篇论文可能还是很有用的。 - j_random_hacker

同时了解出版日期和其他细节将会很有帮助。 - j_random_hacker

Answer 2

Hirschberg's Algorithm嵌入了一个几乎等同于C语言的JavaScript实现。

- user2832537

Answer 3

虽然不是C++，但我认为Python也可以使用。

http://wordaligned.org/articles/longest-common-subsequence

- Aftershock