efektywna najdłuższa biblioteka algorytmów wspólnego podciągania?

Question

Poszukuję efektywnej implementacji algorytmu LCS do użycia w programie C++. Wejścia są dwoma losowymi sekwencjami dostępu do liczb całkowitych.
Używam obecnie metody programowania dynamicznego na stronie wikipedia poświęconej LCS. Jednak ma ono O (mn) zachowanie w pamięci i czasie i umiera na mnie z powodu braku błędów pamięci dla większych wejść.
Przeczytałem o algorytmie Hirschberga, który znacznie poprawia wykorzystanie pamięci, Hunt-Szymański, Masek i Paterson. Ponieważ nie jest to łatwe do wdrożenia, wolę wypróbować je na moich danych z istniejącą implementacją. Czy ktoś wie o takiej bibliotece? Mogę sobie wyobrazić, że skoro narzędzia do porównywania tekstu są dość powszechne, to w okolicy powinny znajdować się jakieś biblioteki open source?

Answer 1

Wyszukując podobne rzeczy, wypróbuj stronę scholar.google.com. Znacznie lepiej jest znaleźć prace naukowe. Okazało się, że ten dokument to "przegląd najdłuższych algorytmów wspólnych podciągów".

Answer 2

Nie C++, ale Python, ale myślę, że jest użyteczny.

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

Answer 3

Hirschberg's Algorithm osadza javascript realizacji: prawie C.