Obliczanie najdłuższego wspólnego podłańcucha dwóch łańcuchów przy użyciu tablic sufiksów

Po tym, jak nauczyłem się, jak budować tablicę sufiksów w złożoności , jestem zainteresowany odkrywaniem zastosowania tablic sufiksów. Jednym z nich jest znalezienie najdłuższego wspólnego podłańcucha między dwoma łańcuchami w czasie . W Internecie znalazłem następujący algorytm:$O(N)$$O(N)$

1. połącz dwa ciągi $A$ i $B$ w jeden ciąg $AB$
2. obliczyć tablicę przyrostków $AB$
3. obliczyć tablicę $LCP$ (najdłuższy wspólny prefiks)
4. odpowiedzią jest największa wartość $LCP[i]$

Próbowałem go zaimplementować, ale ponieważ nie podano wielu szczegółów implementacji (tj. Podczas łączenia łańcuchów, czy powinienem umieścić między nimi znak specjalny ( )?), Mój kod zawiódł w wielu przypadkach testowych. Czy ktoś mógłby dopracować ten algorytm?$AcB$

Z góry dziękuję.

Uwaga: Nie gwarantuję poprawności tego algorytmu; Znalazłem go na blogu i nie jestem pewien, czy to działa. Jeśli uważasz, że jest niepoprawny, zasugeruj inny algorytm.

Twój algorytm jest niepoprawny . Zakładam, że wiesz, jak obliczyć tablicę sufiksów i tablicę LCP łańcucha, czyli ich efektywną implementację. Jak wskazano w komentarzach, powinieneś spróbować zrozumieć, czym jest każdy składnik i dlaczego działa.

Przede wszystkim jest tablica przyrostków ( S S A [ i ] $SA$ ) ciągu. Tablica sufiksów to w zasadzie wszystkie sufiksy ciągu ułożone w porządku rosnącym leksykograficznym. Dokładniej, stosunek wskazuje, że przyrostek od pozycji S A [ I ] ma miejsce I$S$$SA[i]$$S$$SA[i]$$i$ w kolejności leksykograficznym wszystkich przyrostkami z .$S$

Dalej jest tablica L C P [ i ] wskazuje długość najdłuższego wspólnego prefiksu między sufiksami zaczynając od S A [ i - 1 ] i S A [ i $LCP$$LCP[i]$$SA[i-1]$$SA[i]$ . Oznacza to, że śledzi długość najdłuższego wspólnego przedrostka spośród dwóch kolejnych sufiksów gdy są ułożone w kolejności leksykograficznej.$S$

Jako przykład rozważ ciąg . Sufiksy w porządku leksykograficznym to { a , a b b a b c a , a b c a $S = abbabca$ , więc S $\{a, abbabca, abca, babca, bbabca, bca, ca\}$ , 0 ] . dla tablicy 1-indeksowanej. Tablica L C P będzie miała postać L C P = [ - , 1 , 2 , 0 , 1 , $SA = [7, 1, 4, 3, 2, 5, 6]$$LCP$$LCP = [-, 1, 2, 0, 1, 1, 0]$

Teraz, biorąc pod uwagę dwa ciągi i B , łączymy je jako S = A # $A$$B$$S = A\#B$ , gdzie to postać nie występuje zarówno A i B . Powodem wyboru takiego znaku jest to, że przy obliczaniu LCP dwóch sufiksów powiedz a b # d a b d a $\#$$A$$B$$ab\#dabd$ , porównanie będzie zerwać pod koniec pierwszego ciągu (ponieważ występuje tylko raz, dwa różne sufiksy nigdy nie będą miały tej samej pozycji) i nie będą„przelewały się”na drugi ciąg.$abd$

Teraz można zauważyć, że powinieneś być w stanie zrozumieć, dlaczego wystarczy zobaczyć kolejne wartości w tablicy (argument opiera się na sprzeczności i na tym, że sufiksy w S A są w porządku leksykograficznym). Sprawdzaj tablicę L C P pod kątem maksymalnej wartości, tak aby dwa porównywane sufiksy nie należały do ​​tego samego oryginalnego ciągu. Jeśli nie należą do tego samego oryginalnego łańcucha (jeden zaczyna się w A, a drugi w B ), wówczas największą taką wartością jest długość największego wspólnego podłańcucha.$LCP$$SA$$LCP$$A$$B$

Jako przykład rozważmy i B = b c . Następnie S = a b c a b c # b c . Posortowane sufiksy to { a $A = abcabc$$B = bc$$S = abcabc\#bc$S A .$\{abc\#bc, abcabc\#bc, bc, bc\#bc, bcabc\#bc, c, c\#bc, cabc\#bc\}$
$\begin{align*} SA &= [4, 1, 8, 5, 2, 9, 6, 3, 7] \\ LCP &= [-, 3, 0, 2, 2, 0, 1, 1, 0] \end{align*}$

Teraz największą wartość , ale dla S A [ 1 ] i S A [ 2 ] , które to rozpoczęcie w łańcuchu A . Więc to ignorujemy. Z drugiej strony, L C, P [ 4 ] = 2 jest S A [ 3 ] (co odpowiada sufiks b , c z B ) i S A [ 4 $LCP[2] = 3$$SA[1]$$SA[2]$$A$$LCP[4] = 2$$SA[3]$$bc$$B$$SA[4]$(odpowiadające przyrostkowi z A ). Jest to więc najdłuższy wspólny podciąg między dwoma łańcuchami. Aby uzyskać rzeczywiste podciąg, bierzesz podciąg o długości 2 (wartość największego możliwego podciągnięcia L C P ) zaczynając od S A [ 3 ] lub S A [ 4 ] , co oznacza b c .$bcabc\#bc$$A$$2$ $LCP$$SA[3]$$SA[4]$$bc$

Algorytm znaleziony online nie jest całkowicie poprawny. Jak wspomniał Paresh, nie powiedzie się w podanym przez niego przykładzie.

Jeśli jednak upewnisz się, że podczas sprawdzania LCP, sprawdzasz tylko LCP podłańcuchów różnych ciągów. Na przykład, jeśli znajdujesz LCS ciągów A i B, musisz upewnić się, że sąsiadujące wpisy tablicy sufiksów podczas sprawdzania LCP nie są z tego samego ciągu.

Więcej informacji tutaj .

Wydaje mi się, że cytowany algorytm powinien rzeczywiście działać, jeśli znak, który nie jest częścią zestawu znaków, jest używany jako separator, a tablice sufiksów / prefiksów są zbudowane w celu wykluczenia wszystkich ciągów zawierających separator, prawdopodobnie intencją projektant. jest to w zasadzie równoważne budowaniu tablic przyrostków / prefiksów dla dwóch oddzielnych ciągów.

byłoby pomocne dla przyszłych referencji, jeśli opublikowałeś link do algorytmu. zwróć uwagę, że wikipedia ma algorytm do tego w pseudokodzie i wielu innych algorytmach. i są implementacje w większości standardowych języków dostępnych online.