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

0

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

0

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[...]Strings/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).

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0