// STRING MATCHING APPROSSIMATO
// P = stringa di cui trovare
// un'occorrenza approssimata in T

#include <iostream.h>

void strm(int m, int n, char P[], char T[])
{
 int i, j, min, D[m][n];

// Inizializzazione della matrice D
 for(i=0;i<n;i++)
   D[0][i]=0;
 for(i=0;i<m;i++)
   D[i][0]=i;

 for(i=1;i<m;i++)
   for(j=1;j<n;j++)
     {
     if(P[i]==T[j])
       min=D[i-1][j-1];
       else min=D[i-1][j-1]+1;
     if(D[i-1][j]+1 < min)
       min=D[i-1][j]+1;
     if(D[i][j-1]+1 < min)
       min=D[i][j-1]+1;
     D[i][j]=min;
     }

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

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


int main()
{
  char T[]=" abadefgt";
  char P[]=" sde";
  strm(4,8,P,T);
}