Edit Distance with reconstruction

edit_distance_reconstruct.cpp

/*
ioana ---> danaia

EDIT DISTANCE
-------------

cuvant1 --->cuvant2

source ---> destinatie

cut ---> cat

u-->replace-->a

1 operatie


diana ----> diana

stergere ---> a

  0 d a i a n a
0
d
i
a
n
a

DP[i][j] = care este costul minim de a transforma primele i caractere in primele j caractere

DP[ 1 ][ 2 ] = 

            dp[i-1][j-1]    , daca source[i] == dest[j]

dp[i][j] = 

dp[1][3] = 1 + min(dp[1][2], dp[0][2], dp[0[3]]) = 1 + min(1,2,3) =  1 + 1 = 2

dp[1][4] = care este costul de a transforma 'd' => 'dian' => 1 + min(2,3,4) = 1 + 2 = 3

                   replace             stergere     inserare
            1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])              

  0 d i a n a
0 0 1 2 3 4 5
d 1 0 1 2 3 4             
a 2 1 1 1 2 3
i 3 2 1 2 2 3    
a 4 3 2 1 2 2
n 5 4 3 2 1 2
a 6 5 4 3 2 1

SOLUTIA = DP[6][5] = 1

operatie de stergere

1. Stergem: 'a'
 
dp[2][1] = costul minim de a transforma "da" -> d => 1 + min(1,0,2) = 1 + 0 = 1
dp[2][2] = costul minim de a transforma "da" -> 'da' -> 'di'
*/

#include <bits/stdc++.h>

using namespace std;


void reconstruct(const vector<vector<string>> &from, const string& str, const string&s, int n, int m) {


      vector<string> ops;

      int i = n, j = m;

      while(i > 0 || j > 0) {

      	       if(from[i][j] == "match") {i--; j--;}

      	       else if(from[i][j] == "replace") {ops.push_back("Inlocuire: '" + string(1, str[i-1]) + "'-->'" + string(1, s[j-1]) + "'"); i--; j--;}

      	       else if(from[i][j] == "insert") {ops.push_back("Inserare: '" + string(1, s[j-1]) + "'"); j--;}


      	       else if(from[i][j] == "delete") {ops.push_back("Stergere: '" + string(1, str[i-1]) + "'"); i--;}
      }

      reverse(ops.begin(), ops.end());

      cout<<"Operatii: \n";

      for(int k = 0; k < (int)ops.size(); ++k) cout<<k+1<<". "<<ops[k]<<"\n";

      cout<<"\n";	

}


void solve() {

     string str, s;

     cout<<"Source = ";
     cin>>str;

     cout<<"Destination = ";
     cin>>s;

     int n = str.size(), //dimensiunea sursei
         m = s.size();//dimensiunea destinatiei

     vector<vector<int>> dp(n+1, vector<int>(m+1)); 
     //DP[i][j] = costul minim pentru a transforma primele i caractere in primele j caractere

     //DP[i-1][j] = costul minim de a transforma primnele i -1 caractere in primele j caractere

     vector<vector<string>> from(n+1, vector<string>(m+1,""));//pentru reconstruirea solutiei


     //prima coloana
     for(int i = 0; i <= n; ++i) { dp[i][0] = i;  from[i][0] = "delete";}

     	//prima linie
    	for(int j = 0; j <= m; ++j) { dp[0][j] = j;  from[0][j] = "insert";}

        from[0][0] = "start"; 

    		for(int i = 1; i <= n; ++i) {

    			  for(int j = 1; j <= m; ++j) {

                        if(str[i-1] == s[j-1]) {

                        	  dp[i][j] = dp[i-1][j-1];

                        	  from[i][j] = "match";

                        }  else  {
        
                           int best = min({dp[i-1][j-1], dp[i][j-1], dp[i-1][j]});       
                           dp[i][j] = 1 + best;

                           if(best == dp[i-1][j-1])    from[i][j] = "replace";
                           else if(best == dp[i][j-1]) from[i][j] = "insert";
                           else                        from[i][j] = "delete";   
                        }

    			  }
    		}


    		cout<<"Edit Distance = "<<dp[n][m]<<"\n";


    		reconstruct(from, str, s, n, m);
}




int main(int argc, char const *argv[])
{

	solve();//edit distance in action

	return 0;
}