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

我正在寻找在C++程序中使用的LCS算法的（空间）高效实现。输入是两个随机访问整数序列。
我目前使用维基百科页面关于LCS的动态编程方法。但是，这在内存和时间上具有O（mn）行为，并且对于较大的输入而言会因为内存不足错误而死亡。
我已经阅读了Hirschberg的算法，它大大提高了内存使用率，Hunt-Szymanski和Masek和Paterson。由于实现这些并不是微不足道的，所以我宁愿用现有的实现在我的数据上尝试它们。有谁知道这样的图书馆？我会想象，因为文本差异工具很常见，应该有一些开源库吗？高效的最长公共子序列算法库？

来源

2010-09-07 BuschnicK

您是否有兴趣在实际的最长公共子或只是它的长度？ – IVlad 2010-09-07 14:08:49

我需要实际的顺序。 – BuschnicK 2010-09-07 14:35:41

对一些快速的网页搜索感到失望并没有发现任何特别有用的东西（C语言中'char'的特殊实现的加载，但没有Hirschberg的线性空间加速或模板化C++的元素类型）。如果你找到（或创建：D）任何东西，请更新！ – 2010-09-08 06:04:24

当您搜索类似的东西时，请尝试使用scholar.google.com。找到学术作品要好得多。它变成了 http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf 这个文件，“调查最长的公共子序列算法”。

来源

2010-09-09 06:16:30 Lagerbaer

因为OP确实希望所述算法的库实现而不是描述，所以咒语+1。但无论如何可能是一篇有用的论文。 – 2010-09-09 10:42:00

此外，这将有助于了解发布日期和其他详细信息。 – 2010-09-09 10:45:00

不是C++，但Python，但我认为可用。

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

来源

2011-09-22 12:34:44 Aftershock

Hirschberg's Algorithm嵌入一个JavaScript实现：几乎C.

来源

2013-09-30 20:03:07 user2832537

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

回答

相关问题