thư viện thuật toán thuật toán phổ biến dài nhất có hiệu quả?

Question

Tôi đang tìm một (không gian) thực hiện hiệu quả thuật toán LCS để sử dụng trong chương trình C++. Đầu vào là hai chuỗi truy cập ngẫu nhiên của các số nguyên.
Tôi hiện đang sử dụng phương pháp lập trình động từ trang wikipedia về LCS. Tuy nhiên, điều đó có O (mn) hành vi trong bộ nhớ và thời gian và chết trên tôi với ra khỏi bộ nhớ lỗi cho đầu vào lớn hơn.
Tôi đã đọc về thuật toán của Hirschberg, giúp cải thiện đáng kể dung lượng bộ nhớ, Hunt-Szymanski và Masek và Paterson. Vì nó không phải là tầm thường để thực hiện những tôi muốn thử chúng trên dữ liệu của tôi với một thực hiện hiện có. Có ai biết thư viện như vậy không? Tôi muốn tưởng tượng vì các công cụ tìm kiếm văn bản khá phổ biến, nên có một số thư viện nguồn mở xung quanh?

Answer 1

Khi tìm kiếm những thứ như vậy, hãy thử scholar.google.com. Nó là tốt hơn cho việc tìm kiếm các công trình học thuật. Nó bật lên http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf tài liệu này, "khảo sát các thuật toán phổ biến nhất về sau".

Answer 2

Không phải C++ nhưng Python nhưng tôi nghĩ có thể sử dụng được.

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

Answer 3

Hirschberg's Algorithm nhúng một thi javascript: gần như C.