Algoritmo di Knuth-Morris-Pratt

[BHK1]

int findpat(char *string, char *pat)
{
int i,j, start=0; //indice di corrispondenza fra carattere iniziale del pattern e la stringa del testo
int lasts = Lunghezza stringa-1;  //indice dell'ultimo carattere del testo
int lastp = Lunghezza pattern - 1;  //indice iniziale in cui nel testo potremmo trovare lo stesso carattere che chiude il pattern
int endmatch = lastp;  //segna posto del carattere finale del pattern
for(i=0; endmatch<=lasts; endmatch++, start++)  //cicla finchè l'endmatch non è maggiore o uguale alla lunghezza della stringa.
{
   if(stringa[endmatch] == pat[lastp]) //se l'endmatch corrisponde all'ultimo carattere della stringa esegue il for
      for(j=0, i=start; j<lastp && stringa[i]==pat[j]; i++, j++) //una condizione verifica che i caratteri corrispondano, l'altra controlla che j sia sempre minore di lastp, quando questa ultima condizione si verifica allora abbiamo una occorrenza
           ;
   if(j == lastp) return start;//j è stato incrementato per ogni coppia di caratteri uguali (contigui) se j = a lastp abbiamo un occorenza
}
return -1;
}

Sono arrivato a questo algoritmo che migliora la "ricerca banale" di pattern su una stringa, potete spiegarmi come funziona l'algoritmo di Knuth-Morris-Pratt, in maniera semplice?

[Rggb1]

Uichipedia è annerita per oggi, ma questo va benone (anzi, forse meglio).
http://www.inf.fh-flensburg.de/lang/alg ... /kmpen.htm

[apatriarca]

Utilizza il tag code per inserire il codice e cerca di scrivere i tuoi commenti in modo che le linee non siano troppo lunghe. Ti ho modificato il post in modo da fare la prima delle due cose (osserva che è necessario farlo o il codice potrebbe non essere leggibile in quanto alcune parti del codice potrebbero essere interpretate come tag). Per quanto riguarda il problema, il link di Rggb mi sembra ben fatto.

[BHK1]

Allora, dato un pattern di k elementi, definiamo prefisso, l'insieme dei caratteri del pattern $pref={p_0,p_1,...p_(k-b)}$
e suffisso come $suf={p_(k-c),..p_(k-2),p_(k-1)}$
esempio "ananas" ha come prefisso {$epsilon$,a,an,ana,anan,anana} e come suffisso {$epsilon$,s,as,nas,anas,nanas}
l'intersezione dei due insiemi ci da il bordo {$epsilon$}.
Quando confrontiamo la stringa e il pattern carattere per carattere ogni qual volta il confronto fallisce spostiamo il pattern di una posizione in avanti anche se non c'è corrispondenza neanche con il primo elemento;
per evitare shift inutili, ogni qual volta c'è un mismatch spostiamo il pattern di w-r dove w corrisponde alla lunghezza del prefisso più lungo e r alla lunghezza del bordo più lungo.
giusto?