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

15

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.

Rontogiannis Aristofanis
źródło
3
Przed wdrożeniem algorytmu spróbuj zrozumieć, dlaczego on działa. To mogłoby pomóc odpowiedzieć na pytanie, jak połączyć dwa ciągi.
Yuval Filmus,
3
Wątpię w poprawność tego algorytmu. Weź i , tak jak to czytam, zwróci , co jest złe. b c d a b c dabcdabcdbcdabcd
Khaur

Odpowiedzi:

20

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 ] SSA ) 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 ISSA[i]SSA[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 ]LCPLCP[i]SA[i1]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=abbzabdoza , więc S A{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 , 1SA=[7,1,4,3,2,5,6]LCPLCP=[,1,2,0,1,1,0]

Teraz, biorąc pod uwagę dwa ciągi i B , łączymy je jako S = A # BABS=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#ABab#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.LCPSALCPAB

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

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]=3SA[1]SA[2]ALCP[4]=2SA[3]bcBSA[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#bcA2 LCPSA[3]SA[4]bc

Paresh
źródło
1
Doskonałe wytłumaczenie, ale myślę, że przykład jest nieco źle, sortowanie przyrostki to: {#bc,abc#bc,abcabc#bc,bc,bc#bc,bcabc#bc,c,c#bc,cabc#bc}, SA=[7,4,1,8,5,2,9,6,3]iLCP=[−,0,3,0,2,2,0,1,1]
Saúl Martínez Vidals
1

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 .

rohitjv
źródło
1
Kiedy mówisz „Ta odpowiedź”, masz na myśli swoją własną czy inną odpowiedź? Proszę używać tylko pola odpowiedzi, aby odpowiedzieć na pytanie, a nie komentować innych odpowiedzi. Gdy zdobędziesz wystarczającą liczbę reputacji, będziesz mógł komentować inne odpowiedzi.
David Richerby
0

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.

vzn
źródło