Mamy słowo, powiedzmy acecbaabca. Sufiksy to końcowe fragmenty słowa, czyli a, ca, bca, itd. Za pomocą jednego przeglądnięcia słowa chcemy znaleźć sufiks leksykograficznie [czyli alfabetycznie] ostatni.
Weźmy zatem słowo abcbacbacbd. Fragment cba to okresowy fragment słowa – liczymy na to, że będzie się on powtarzać. Jeśli nic się nie powtarza, to całe słowo jest okresem, przy czym słowo może być okresowe z ułamkową wielokrotnością. T[] oznacza aktualnie sprawdzane miejsce, p – najlepszy możliwy okres fragmentu k…i, czyli jak najmniejszy, k - ostatni alfabetycznie sufiks do tej pory, i – indeks sprawdzanego miejsca. Będziemy pamiętać najlepszy sufiks od k do i., oczywiście k<=i. W miejsce (i-k)%p będziemy przestawiać k. Słowo przeglądamy od lewej.
Pseudokod:
k=1
p=1
i=2
while ( i <= | T| ) // T – długość słowa
j = k + ( i–k )%p;
if T [i] = T [j]
i++ ;
else
if T [i] < T [j ]
p= i - k +1
i ++ ;
else
if T [i] > T [j]
k=i - ( i–k )% p ;
i=k+1;
p=1;
Czyli widać, że mamy trzy przypadki. Jeśli trafiliśmy na literę, której się spodziewaliśmy, to idziemy dalej. Jeśli słowo przestaje być okresowe, ale sufiks dalej jest najlepszy, to k zostaje na miejscu. Jeśli trafiliśmy na lepszą literę, czyli ten nowy sufiks jest lepszy, k musi się przestawić, i traktujemy to jak początek słowa, zapominając jakby o dalszej części tekstu, a okres znowu jest równy 1. Oczywiście można sobie poradzić bez używania j.
Jaka będzie złożoność? Nie wykonamy więcej iteracji niż 2 razy długość słowa. Za każdą iteracją zwiększa się i+k, bo k zawsze idzie do przodu co najmniej najmniej o p, a i nie cofnie się więcej niż o p. Maksymalna możliwa wartości i+k <= 2 |T|.
Algorytm działa zatem w O(n).
