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)| .