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:
- połącz dwa ciągi i w jeden ciąg
- obliczyć tablicę przyrostków
- obliczyć tablicę (najdłuższy wspólny prefiks)
- odpowiedzią jest największa wartość
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?
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.
algorithms
suffix-array
Rontogiannis Aristofanis
źródło
źródło
Odpowiedzi:
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 IS 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= a b b a b ca , 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] LCP LCP=[−,1,2,0,1,1,0]
Teraz, biorąc pod uwagę dwa ciągi i B , łączymy je jako S = A # BA 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# 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 bA=abcabc B=bc S=abcabc#bc S A .{abc#bc,abcabc#bc,bc,bc#bc,bcabc#bc,c,c#bc,cabc#bc}
SALCP=[4,1,8,5,2,9,6,3,7]=[−,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]=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
źródło
{#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]
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 .
źródło
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.
źródło