Algorytmy tekstowe mają decydujące znaczenie przy wyszukiwaniu informacji typu tekstowego, ten typ informacji jest szczególnie popularny w informatyce, np. w edytorach tekstowych i wyszukiwarkach internetowych. Tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą x[1,…,n], elementami której są symbole ze skończonego zbioru A (zwanego alfabetem). Liczba n=|x| jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.
Algorytmy na tekstach wyróżniają się tym, że wykorzystują specyficzne, kombinatoryczne własności tekstów. Okresem tekstu x jest każda niezerowa liczba naturalna p taka, że x[i]=x[i+p], dla każdego i, dla którego obie strony są zdefiniowane. Przez per(x) oznaczmy minimalny okres x.
Pojęciem dualnym do okresu jest prefikso-sufiks tekstu. Jest to najdłuższy właściwy (nie będący całym tekstem) prefiks tekstu x będący jednocześnie jego sufiksem. Oczywiste jest, że |x|−per(x) jest długością prefikso-sufiksu x. Jeśli per(x)=|x| to prefikso-sufiksem x jest słowo puste o długości zerowej.
Oznaczmy przez P[k] rozmiar prefikso-sufiksu x[1..k]. Zatem per(x)=n−P[n], gdzie n=|x|.
Przykład
Dla x = abababababb mamy:
P[1..11] = [0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0].
Wartość P[0] jest wartością sztuczną (przyjmiemy, że P[0]=−1).
Wprowadzimy również tablicę ‘’'silnych prefikso-sufiksów dla wzorca x[1..m]: jeśli j<|x|, to P′[j]=k, gdzie k jest maksymalnym rozmiarem słowa będącego właściwym prefiksem i sufiksem x[1..j] i spełniającego dodatkowy warunek x[k+1]≠x[j+1] dla j<n.
Jeśli takiego k nie ma, to przyjmujemy P′[j]=−1.
Przyjmujemy ponadto, że P′[m]=P[m].
Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P.
Przykład
Dla x = abaab mamy:
P[0..5] = [−1, 0, 0, 1, 1, 2 ]; P′[0..5] = [−1, 0, −1, 1, 0, 2 ].