Trzy twierdzenia

Twierdzenie 1.
Algorytm Boyera-Moore'a wykonuje co najwyzej 4n porownan

Defniujemy punkt krytyczny w slowie jako pozycje w slowie
ktora jest poczatkiem krotszego z dwoch maksymalnych
sufiksow,w normalnym i odwroconym porzadku alfabetu.

Twierdzenie 2.
W punkcie krytycznym minimalny lokalny okres
jest globalnym okresem.

Twierdzenie 3.
Poprawnosc algorytmu Fredricksona-Maiorany.
Konkatenacja kolejnych (w porz. leks.) slow Lyndona
o dlugosci bedacej dzielnikiem n jest ciagiem de Bruijna
rzedu n ( w szczegolnosci ma dlugosc 2^n).

Twierdzenie 4. (o rownowaznosci kwadratowej tekstow)
Poprawnosc algorytmu sprawdzajacego rownowaznosc dwoch slow
dla rownowaznosci xx rownowazne x (dla dowolnego podslowa x).