[C++] "String Matching" con Knuth-Morris-Pratt

[Neptune]

Ho sottomano il seguente algoritmo di string matching di knuth-Morris-Pratt sviluppato in C++ e stavo cercando di apprenderne al meglio come funziona per un esame in visita.
Qualcuno può aiutarmi un pò magari aggiungendo qualche commento qua e la?

#include <iostream>
#include<cstring>
#include<string>
#define NIL -1

using namespace std;
typedef char pattern[21];
typedef char text[100];
typedef int vettore[20];

/*Questa funzione scansione il pattern da ricercare in modo da permettere a kmp di effettuare un backtrack intelligente,
 * nella fattispecie associa ad ogni lettera del pattern la lunghezza del backtrack da effettuare in caso di discordanza di
 * caratteri.*/
void spostamenti(pattern p, vettore s){
   int m = strlen(p);
   s[0] = 0; //spostamento al primo carattere è sempre 0
   int k = 0; //spostamento (cambierà nel ciclo)
   for (int q = 2; q <= m; q++){
      while ((k > 0) && (p[k] != p[q-1]))
      {
         k = s[k-1];
         cout << "K1 =" << k << endl;
      }
      if (p[k] == p[q-1])
      {
         k++;
         cout << "K2 =" << k << endl;
      }
      s[q-1] = k;
   }
}

int kmp(text t, pattern p){
   vettore s;
   spostamenti(p, s);
   for(int i = 0; i < 20; i++)
	   cout << s[i] << endl;
   int risposta = -1;
   int q = 0;
   int m = strlen(p);
   int n = strlen(t);
   if (n >= m){
      for (int i = 0; (i < n && q != m); i++){
         while ((q > 0) && (p[q] != t[i]))
         {//finché non combaciano i caratteri di testo e pattern
            q = s[q-1]; // torna indietro di s[q-1] passi nel pattern
         }
         if (p[q] == t[i])
            q++; // se trova corrispondenza confronta il successivo carattere di testo e pattern
         if (q == m) //se q è l'm-esimo carattere vuol dire ke ha trovato un'occorrenza di p in t
            risposta = i + 1 - m; //indice della prima occorrenza
      }
   }
   return risposta+1; // se non trova occorrenze restituisce 0
}


int main (int argc, char * const argv[]) {
	cout << "dovrebbe trovarlo" << endl;
    char contenitore[]= "101100101011\0";
	char contenuto[] = "10110110\0";
	
	cout << kmp(contenitore, contenuto);

    return 0;
}

Quello che ho capito dopo ore che lo guardo e cerco su internet è che la funzione spostamenti decide di quanto tornare indietro nei confronti (di quanto effettuare il backtrack) in caso occorre una disguaglianza tra caratteri (visto che al contrario della ricerca bruta dovrebbe essere un pochino più ottimizzato);

Ho anche capito che quanto deve tornare indietro è calcolato a seconda delle occorenze di sottostringhe uguali;

Come calcolare la lunghezza dei salti indietro però non sono riuscito a capirlo. So solo che effettuato il salto indietro dovrebbe reiniziare a controllare dalla prima lettera della parola da ricercare.

Purtroppo anche con le opportune cout mi sfugge qualcosa e non riesco a capire come si calcola la lunghezza dei salti, per quanto l'algoritmo sono cinque righe in croce. Sarà l'orario.

Se qualcuno mi aiuta avrà tutta la mia gratitudine

[ramy89]

Non credo che questo forum sia utile al tuo caso,qua si tratta di interpretare un codice già scritto da un' altra persona,se non da errori non posso fare molto.
L' unica sarebbe provare ad eseguirlo,ma se non da errore cosa dovremmo fare?

[Neptune]

Originariamente inviato da ramy89
Non credo che questo forum sia utile al tuo caso,qua si tratta di interpretare un codice già scritto da un' altra persona,se non da errori non posso fare molto.
L' unica sarebbe provare ad eseguirlo,ma se non da errore cosa dovremmo fare?

Credevo che magari qualcuno che conosce il suddetto algoritmo o un pochino più sveglio di me nel capire l'atrui codice (non sono mai stato una cima) riusciva a colpo d'occhio a dirmi cos'è che fa quella seconda funzioncina d'appoggio nel particolare