Opiszemy teraz błyskotliwy algorytm Karkkainena-Sandersa ( w skrócie KS) będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR oblicza znacznie więcej niż tablica sufiksowa, ponieważ konstruuje słownik podsłów bazowych wielkości \( n \log n \) (mający liczne inne zastosowania, ale jako całość być może niepotrzebny przy liczeniu tablicy sufiksowej)
Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozbijmy zbiór pozycji [1..n] tekstu \( x \) na dwa zbiory N, M :
Zbiór N składa się z co trzeciej pozycji, a M jest zbiorem pozostałych pozycji.
N = {3,6,9,12,15,....}, M = {1,2,4,5,7,8,10,11,...}
Przez \( SUF[M] \), oznaczmy tablicę sufiksową dla pozycji ze zbioru \( M \), podobnie zdefiniujmy \( SUF[N] \).
\( SUF[M] \) daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru \( M \).
Dla początkowego przykładowego tekstu \( x\ =\ babaabababba\# \) mamy
\( M\ =\ \{1,2,4,5,7,8,10,11\}\ \ \ \ \ N\ =\ \{3,6,9,12\} \)
\( SUF[M]\ =\ [4,\ 2,\ 5,\ 7, \ 1, \ 8,\ 11,\ 10]\ \ \ \ SUF[N]\ =\ [ 9,\ 12,\ 3,\ 6,] \)
Sprowadzenie obliczania \( SUF[M] \) do obliczania tablicy sufiksowej rozmiaru \( \frac{2}{3}n \)
Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie \( x \) korzystając z radix-sort. Każdemu takiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy \( kod(z) \) otrzymaną nazwę podsłowa długości 3. Zakładamy, że \( x \) kończy się dodatkowo dwoma symbolami \( \# \), ale rozważamy tylko podsłowa zaczynające się w \( x \). Dla uproszczenia załóżmy, że 3 jest dzielnikiem n.
Tworzymy nowe słowo \( compress(x) \) w następujący sposób:
\( y2\ =\ kod(a_2a_3a_4)\cdot kod(a_5a_6a_7) \ldots kod(a_{n-1}a_{n}a_{n+1}) \)
\( compress(x) \ =\ y1 \& \ y2\ \) ; gdzie \( \& \) jest nowym maksymalnym symbolem
Przykład. Weźmy początkowy przykład \( x\ = \ babaababbba\# \), gdzie \( \# \)jest większe niże a,b. Mamy
\( aab \prec aba\prec bab \prec ba\# \prec bba \), Zatem kody tych trójek są kolejno \( 1,\ 2,\ 3,\ 4, \ 5 \).
Oznaczmy\( kod(z)= < z> \). Wtedy
\( y1\ =\ < bab> < aab> < aba> < bba>\ =\ 3\ 1\ 2\ 5 ; \)
\( y2\ =\ < aba> < aba> < bab> < ba\#>\ =\ 2\ 2\ 3\ 4 \)
\( compress(x)\ =\ =\ 3\ 1\ 2\ 5 \ \& \ 2\ 2\ 3\ 4\ \),
Jeśli mamy tablicę sufiksową dla słowa \( compress(x) \), można łatwo obliczyć \( SUF[M] \) w czasie liniowym. Pozostawiamy to jako ćwiczenie.
Algorytm \( {\Large KS} \) (Karkkainen-Sanders)
x':= compress(x); obliczamy tablicę sufiksową dla x' rekurencyjnie; obliczamy SUF[M] w czasie liniowym, znając tablicę sufiksową dla x'; obliczamy SUF[N] w czasie liniowym (bez rekursji), znając SUF[M]; scalamy posortowane ciągi SUF[M], SUF[N] w tablicę sufiksową dla całego słowa x
Krok 1 algorytmu sprowadza się do radix-sortu, podobnie jak w algorytmie KMR. Kroki 3,4 są proste i ich implementację pozostawiamy czytelnikowi jako ćwiczenie.
Najważniejszy jest krok scalania. Mamy dwie posortowane listy sufiksów i trzeba je scalić w jedną posortowaną listę. Zasadniczym problemem jest implementacja operacji porównania leksykograficznego dwóch (długich) sufiksów w czasie stałym. Jeśli oba sufiksy są typu \( M \) lub oba są typu \( N \), to porównanie jest w czasie stałym, bo mamy posortowane listy takich sufiksów.
Pokażemy na przykładzie kluczową operację porównania sufiksu typu M z sufiksem typu N w czasie stałym.
Przykład
Nierówność \( sufiks_2 < sufiks_{12} \) jest równoważna temu, że zachodzi co najmniej jeden z warunków:
1. \( (a_2 < a_{12}) \)
2. \( \ (a_2=a_{12}, a_3 < a_{13}) \)
3. \( (a_2=a_{12}, a_3=a_{13}, sufiks_4 < sufiks_{14}) \)
Jednakże \( 4,14\in M \), zatem \( sufiks_4 \) i \( sufiks_{14} \), są typu M i można je porównać w czasie stałym.
Niech \( T(n) \) będzie czasem działania algorytmu KS. Zachodzi
\( T(n) \ =\ T(\lceil \frac{2}{3}\cdot n \rceil) + O(n) \)
Rozwiązaniem jest \( T(n)=O(n) \). Mamy więc liniowy algorytm liczenia tablicy sufiksowej. Daje to również liniowy algorytm konstrukcji drzewa sufiksowego.
Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bez korzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena). W algorytmach tych współczynnik przy złożoności liniowej wynosi \( \log |A| \), gdzie A jest alfabetem.