Algorytm Knutha Morrisa Pratta

Algorytm Knutha-Morrisa-Pratta wyszukuje w czasie zamortyzowanym liniowym od dlugosci (n) tekstu (T), po uwcześniejszym obliczeniu funkcji prefiksowej dla wzorca P, wszystkie wystąpienia wzorca P w tekscie T (mogą zachodzić na siebie).

int pi[1000001], m, n; //tablica pi musi zostac wypelniona przez knuth_pi(), m - dlugosc wzorca P, n - dlugosc tekstu T
 
char T[2000001];
 
char P[1000001];
 
int max(int value1, int value2){return ( (value1 > value2) ? value1 : value2); } //zwraca maximum z dwoch wartosci
 
void kmp(){
 
     int i=1, j=0;
 
     while (i<=n-m+1){ //sprawdzamy caly T az do ostatniej mozliwej pozycji poczatkowej wystapienia wzorca P
 
        j=pi[j];
 
        while((j<m) && (P[j]==T[i+j-1])) j++;
 
        if (j==m) {}//znaleziono wystapienie wzorca P w tekscie T na pozycji i
 
        i=i+max(1,j-pi[j]);
    }
}