Albo ja jestem cioł, albo oni na MiMie mają więcej literówek, niż klawiszy na klawiaturze. Absolutnie nie wykluczam pierwszej możliwości.

Próbuję sobie przyswoić to: http://smurf.mimuw.edu.pl/node/384

Pokażemy pewne proste zastosowanie tablic prefikso-sufiksów. Słowem pokrywającym tekst x jest każdy taki tekst y, którego wystąpienia w x pokrywają cały tekst x. Na przykład słowo y=aba pokrywa tekst x=ababaaba, natomiast nie pokrywa tekstu abaaababa. Zajmiemy się problemem: obliczyć w czasie liniowym długość najkrótszego słowa pokrywającego dany tekst x.

Niech S[i] będzie rozmiarem minimalnego słowa pokrywającego tekst x[1..i].

Następujący algorytm oblicza długość minimalnego słowa pokrywającego tekstu x. Algorytm jest efektywny ponieważ liczy dodatkową tablicę Zakres. W i-tej iteracji algorytmu pamiętany jest znany dotychczas zakres każdego minimalnego słowa pokrywającego.

title

Rysunek 1: i-ta iteracja algorytmu dla i=15 oraz słowa x = abaabababaababa…. Tuż przed rozpoczęciem tej iteracji mamy P[i]=8, S[8]=2, Zakres[3]=13. Zatem spełniony jest warunek i−Zakres[S[P[i]]≤S[P[i]]. Po zakończeniu i-tej iteracji mamy S[15]=3,Zakres[3]=15.

(W ichniej nomenklaturze P to tablica prefikso-sufiksów, czyli że P[i] przechowuje rozmiar najdłuższego właściwego prefiksu słowa x[1..i], który jest jednocześnie sufiksem tego słowa).

Nic nie rozumiem. Po pierwsze, skoro słowa są indeksowane u nich od 1 a nie od 0, to i=15 wskazuje na literkę a, a nie b, jak pokazuje strzałka na rysunku. Po wtóre, jakim prawem S[8]=2?! Dla pierwszych ośmiu liter, jakby nie patrzeć, minimalne słowo pokrywające to aba, a więc słowo trzyliterowe?! Jak oni chcą pokryć abaababa słowem dwuliterowym?

Czy to ja czegoś nie rozumiem, czy oni mają literówki?