Najdłuższy wspólny podciąg ciągu binarnego.

Rejestracja: dni
Ostatnio: dni
Postów: <a title="Znajdź posty tego użytkownika" :href="`/Forum/User/${post.user.id}`" style="text-decoration: underline">2

2014-08-31T11:36:03+02:00

Czy istnieje algorytm wyznaczający w czasie O(n*log₂n) najdłuższy wspólny podciąg ciągu binarnego ?

2014-09-01T03:00:39+02:00

Dajesz xor na obu ciągach i szukasz najdłuższego ciągu 0.

EDIT: Rypłem się trochę, ale znalazłem rozwiązanie http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/86.IPL.html (jeśli długość ciągu A będzie mniejsza lub równa słowu na danym komputerze to algorytm będzie liniowy względem długości słowa B).