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,\ldots,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]\ne 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\ ]. \)