高效的最長公共子序列算法庫？

我正在尋找在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

高效的最長公共子序列算法庫？

回答

相關問題