我正在寻找用于 C++ 程序的 LCS 算法的（空间）高效实现。输入是两个随机访问整数序列。
我目前正在使用关于 LCS 的维基百科页面中的动态编程方法。但是，这在内存和时间上有 O(mn) 的行为，并且在我身上死掉了，因为更大的输入会出现内存不足的错误。
我已经阅读了 Hirschberg 的算法，它可以显着提高内存使用率，Hunt-Szymanski 以及 Masek 和 Paterson。由于实现这些并非易事，我更愿意使用现有实现在我的数据上尝试它们。有人知道这样的图书馆吗？我想既然文本差异工具很常见，应该有一些开源库吗？
问问题
5332 次
3 回答
3
在搜索类似的内容时，请尝试 Academic.google.com。寻找学术著作要好得多。它出现了 http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf 这个文件，“最长公共子序列算法调查”。
于 2010-09-09T06:16:30.320 回答
0
不是 C++，而是 Python，但我认为可用。
于 2011-09-22T12:34:44.810 回答
0
Hirschberg 的算法嵌入了一个 javascript 实现：几乎是 C。
于 2013-09-30T20:03:07.433 回答