Matematyka.pl

Witam,
Czy istnieje jakaś pomocna struktura danych która pomoże mi szukać najkrótszego okresu słowa.
Z tym że tych słów będzie dużo więć \(\displaystyle{ O(n^2)}\) odpada ;(.
Czekam na propozycje

Wystarczy policzyć tablicę prefiksowo-sufiksową (znaną też jako "tablica \(\displaystyle{ \pi}\)", "tablica KMP" albo "partial match", nie mylić z tablicą sufiksową!). Ona przy okazji wyznacza najkrótszy okres słowa.

Tak, myślałem o tym, jednak jedno mi nie pasuje w tym. Funkcja P znajdzie nam najdłuższe właściwe prefixo-sufixy dla słów: s[1...n], s[1..n-1], s[1...n-2]......... itd
ale jeśli ja dostanę pytanie o słowo s[5...9] ?

Ach, chodzi o okresy podsłów danego słowa. Czyżby to zadanie?

zadanie analogia
ale nie to miałem na myśli

Na OI-u napisałem tylko rozwiązanie za 30 pkt., ale wydaje mi się, że w tym zadaniu przydatne będzie haszowanie lub algorytm KMR. W każdym razie na pewno odpowiedź znajdziesz tutaj:

Hm, to co miałeś na myśli?

źle się wyraziłem, w moim zadaniu chodzi o to samo
tyle, ze nie rozwiazuję tego pod to