Funkcja Prefiksowa Knutha

Funkcja prefixowa Knutha oblicza w czasie zamortyzowanym liniowym od dlugosci (m) wzorca (P), dlugosci najdluzszych prefixow wzorca P (pi[q]), ktore są jednoczesnie sufixami P_q.

int pi[1000001], m; //pi to tablica funkcji prefixowej, m - dlugosc wzorca P
 
char P[1000001]; //wzorczec P
 
void knuth_pi(){
 
    pi[0]=0; pi[1]=0; int t=0; //zerujemy pi[0] i pi[1] oraz zmienna pomocnicza t
 
    for (int j=2; j<=m; j++){ //j jest naszym iteratorem, przechodzimy przez caly wzorzec P
 
        while ((t>0) && (P[t]!=P[j-1])) t=pi[t];
 
        if (P[t]==P[j-1]) t++;
 
        pi[j]=t;
    }
}

Efektem działania powyższego kodu jest tablica funkcji prefiksowej Knutha dla wzorca P. Teraz możemy jej użyć w dalszych obliczeniach.