dad_89
27-04-2008, 17:59
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 :(
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 :(