[C] Algoritmo di Knuth-Morris-Pratt

[dad_89]

Sto avendo problemi con quest'algoritmo, non riesco a capire il suo funzionamento, diciamo che la cosa che più mi lascia perplesso è la tabella che viene creata per poter saltare i confronti nella ricerca della sottostringa nella stringa ...

In pratica ho preso sto codice ma non riesco a capire che diamine faccia:

void kmp_init( F , B )
  int  F[];
  char *B;
{
  int t, s, m=strlen( B );
F[0]=-1;
--B;

 // --F; --B;   /* algorithm assumes strings start at index 1 */
  t = F[1] = 0;

  for ( s = 1 ; s < m ; s++ )  {
    while ( t > 0  &&  B[s+1] != B[t+1] ) {
      t = F[t];
    }
    F[s+1] = ( B[s+1] == B[t+1] ) ? ++t : 0;
  }/*for*/

  return;
}/*kmp_init()*/

Non riesco a capire perchè diamine dobbiamo azzerare la stringa, cioè in questo modo => --B non azzero completamente la stringa?, in che modo poi possiamo creare la tabella? Cioè senza il pattern come diamine facciamo? E poi perchè l'array delle occorenze viene impostato alla posizione 0 a -1 (quando da quello che ho capito dovrebbe essere sempre impostato a 0) e perchè il primo elemento sempre del vettore delle occorenze è messo a 1? :?
Scusatemi per i miei dubbi idioti ma proprio non riesco a capacitarmi

[dad_89]

up!

[dad_89]

Nessuno sa darmi una manina piccolina?