h2. Algoritmul KMP

Gaseste toate aparitiile un string $N$ in $M$ in timp {$O(n + m)$}, unde {$n = lungime(N)$}, {$m = lungime(M)$}. O parte esentiala a sa este functia prefix $&#0928; : {1..n} -> {0..n-1}$ unde $&#0928;{~i~}$ = cel mai lung prefix al lui $M$ care este sufix al lui {$M{~i~}$}. Evident, M{~&#0928;{~i~}~} (prefixul de lungime &#0928;{~i~} al lui {$M$}) prefix al lui {$M{~i~}$}, deci {$&#0928;{~i~} < i$}.

Gaseste toate aparitiile unui string $N$ in $M$ in timp {$O(n + m)$}, unde {$n = lungime(N)$}, {$m = lungime(M)$}. O parte esentiala a sa este functia prefix $&pi; : {1..n} -> {0..n-1}$ unde $&pi;{~i~}$ = cel mai lung prefix al lui $M$ care este sufix al lui {$M{~i~}$}. Evident, M{~&pi;{~i~}~} (prefixul de lungime &pi;{~i~} al lui {$M$}) prefix al lui {$M{~i~}$}, deci {$&pi;{~i~} < i$}.

h3. Algoritm_calcul_functie_prefix

mult $n - 1$ ori pe parcursul algoritmului
* => Complexitate : $O(n)$

Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare $i$ in care s-a acceptat {$N{~i~}$}, vedem cat de mult putem lua de la sfarsitul lui {$N{~i~}$} astfel incat sufixul respectiv sa fie prefix pentru {$N$}. De remarcat ca in cazul in care starea candidata $k$ nu este buna, nu mergem in {$k - 1$}, ci in {$Π{~k~}$}. Aceasta este de fapt "magia" care ofera complexitate liniara.

Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare $i$ in care s-a acceptat {$N{~i~}$}, vedem cat de mult putem lua de la sfarsitul lui {$N{~i~}$} astfel incat sufixul respectiv sa fie prefix pentru {$N$}. De remarcat ca in cazul in care starea candidata $k$ nu este buna, nu mergem in {$k - 1$}, ci in {$π{~k~}$}. Aceasta este de fapt "magia" care ofera complexitate liniara.

Algoritmul de potrivire este similar celui al calculului functiei prefix, numai ca aici la fiecare pas $i$ cautam cel mai lung prefix al lui $N$ care este sufix al lui {$M{~i~}$}.