Pokażemy, jak znaleźć liczbę podsłów słowa \( x \) przy pomocy tablicy sufiksowej lub drzewa sufiksowego. Końcowego markera \( \# \) nie traktujemy jako części słowa \( x \). Liczba podsłów jest równa \( |Subwords(x)| \). Jeśli wszystkie symbole słowa są różne to \( |Subwords(x)|={n \choose{2}} \).
Używając drzewa sufiksowego, czas \( O(n) \)
Sumujemy wagi krawędzi drzewa.
Używając tablicy sufiksowej, czas \( O( n) \)
Niech \( SUMA(lcp) \) będzie sumą elementów tablicy \( lcp \). Liczbę podsłów obliczamy jako
\( {n+1\choose{2}}-SUMA(lcp) \)
Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona (korzystając z drzewa sufisowego lub z tablicy sufiksowej).
Przykład
Dla przykładowego tekstu \( x\ = \) mamy \( |Subwords(x)|=55 \). Proponujemy to wyliczyć z tablicy sufiksowej i drzewa sufiksowego dla\( x \), danego na rysunku. Suma elementów tablicy \( lcp \) wynosi 23. Liczba podsłów to: \( 78-23\ =\ 55 \) Podobnie jak tablicę sufiksową możemy zdefiniować tablicę \( ROT \) odpowiadającą posortowanemu ciągowi wszystkich cyklicznych przesunięć słowa \( x \) (rotacji \( x \)).
Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu obliczania tablicy \( ROT \), przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.
Dygresja. Ciekawą klasę słów, dla których tablice \( SUF,\ ROT \) są szczególnie interesujące, stanowią słowa Fibonacciego \( F_n \). W tym szczególnym przypadku załóżmy, że pozycje numerujemy od zera. Dla każdego \( n \) tablica \( ROT \) jest postępem arytmetycznym (modulo długość słowa). Natomiast tablica \( SUF \) jest postępem arytmetycznym, gdy \( n \) jest parzyste.
Słowa Fibonacciego definiujemy następująco:\( F_0=a,\ F_1=ab,\ F_{n+1}\ =\ F_n\cdot F_{n-1} \) Na przykład: \( F_3\ =\ abaab,\ F_4\ =\ abaababa,\ F_5\ =\ abaababaabaab. \) Oznaczmy przez \( SUF_n \) tablicę \( SUF \) dla słowa Fibonacciego \( F_n \); wtedy:
\( SUF_4\ =\ [7\;2\;5\;0\;3\;6\;1\;4], \) \(SUF_5\ =\ [10\;7\;2\;11\;8\;5\;0\;3\;12\;9\;6\;1\;4].\)
Pozostawiamy jako ćwiczenie znalezienie wzoru na \( |Subwords(F_n)| \).