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 teksty
, którego wystąpienia wx
pokrywają cały tekstx
. Na przykład słowoy=ab
a pokrywa tekstx=ababaaba
, natomiast nie pokrywa tekstuabaaababa
. Zajmiemy się problemem: obliczyć w czasie liniowym długość najkrótszego słowa pokrywającego dany tekstx
.Niech
S[i]
będzie rozmiarem minimalnego słowa pokrywającego tekstx[1..i]
.Następujący algorytm oblicza długość minimalnego słowa pokrywającego tekstu
x
. Algorytm jest efektywny ponieważ liczy dodatkową tablicę Zakres. Wi
-tej iteracji algorytmu pamiętany jest znany dotychczas zakres każdego minimalnego słowa pokrywającego.Rysunek 1:
i
-ta iteracja algorytmu dlai=15
oraz słowax = abaabababaababa…
. Tuż przed rozpoczęciem tej iteracji mamyP[i]=8
,S[8]=2
,Zakres[3]=13
. Zatem spełniony jest waruneki−Zakres[S[P[i]]≤S[P[i]]
. Po zakończeniui
-tej iteracji mamyS[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?