// STRING MATCHING APPROSSIMATO
// trovare un'occorrenza approssimata di una stringa pattern P in una stringa testo T

#include <iostream>
#include <cstdio>

using namespace std;

char P[] = "XSDE"; // stringa pattern
int m = 4; // lunghezza della stringa pattern P
char T[] = "ABADEFGT"; // stringa testo 
int n = 8; // lunghezza della stringa testo T

void displayDBtable(int m, int n, int *mat) {
  cout << "   ";
  for(int j = 0; j < n; j++)
    cout << T[j] << "  ";
  cout << endl;

  for(int i = 0; i < m; i++) {
    cout << P[i] << "  ";
    for(int j = 0; j < n; j++)
      if(mat[ i*n + j ] < 0 ) 
         cout << mat[ i*n + j ] << " ";
      else
         cout << mat[ i*n + j ] << "  ";
    cout << endl;   
  }
  cout << endl;   
  cout << "press RETURN to continue ... ";
  getchar();   
  cout << endl;   
}

void strm(int m, int n, char P[], char T[]) {
 int D[m][n];
 /*
 D[i][j] = il numero minimo di modifiche (inserimenti/cancellazioni/cambi di carattere)
           che consenta di trasformare il prefisso P[0..i] del pattern P
           in un suffisso del prefisso T[0..j] del testo.

  in particolare: 
 D[m-1][j] = il numero minimo di modifiche (inserimenti/cancellazioni/cambi di carattere)
           che consenta di trasformare il pattern P
           in un suffisso del prefisso T[0..j] del testo.
 */


// Inizializzazione della matrice D, prima regola
 for(int j=0; j<n; j++)
   if( P[0] == T[j])  D[0][j] = 0;
   else D[0][j] = 1;

// Inizializzazione della matrice D, seconda regola
 bool occurs = false;
 for(int i=0; i<m; i++) {
   if ( P[i] == T[0] ) occurs = true;
   D[i][0] = i + 1 - occurs;
 }
 int min;
 for(int i=1; i<m; i++)
   for(int j=1; j<n; j++) {
     if(P[i] == T[j])  min = D[i-1][j-1];
     else min = D[i-1][j-1] + 1; // pagando 1, puoi sostituire un carattere 

     if(D[i-1][j]+1 < min)  // pagando 1, puoi cancellare un carattere del pattern
         min = D[i-1][j]+1;

     if(D[i][j-1]+1 < min)  // pagando 1, puoi cancellare un carattere del testo
       min = D[i][j-1]+1;

     D[i][j] = min;

   }

   displayDBtable(m, n, (int *) D);


 min = D[m-1][0]; int j_min = 0;
 for(int j=1; j<n; j++)
   if( D[m-1][j] < min ) {
      min = D[m-1][j];
      j_min = j;
   }

  cout << "Un'occorrenza " << min << "-approssimata" << " di " << P << endl;
  cout << "termina nella posizione " << j_min + 1 << " di " << T << endl;
}


int main() {
  strm(m, n, P, T);
}