hi guys
i get wrong answer in this problem
and i don't know why
please if any one know or can help please share it
#include<iostream>
using namespace std;
#include<string>
int EditDistance[30][30];
int Tracing[30][30];
string FirstString,SecondString;
int NoOfDeletions , NoOfAdditions;
int FindMin(int a,int b,int c,int i,int j)
{
if(a<b&&a<c)
{
Tracing[i][j]=2;//Means Replace
return a;
}
else if(a<c)
{
Tracing[i][j]=3;//Means Delete
return b;
}
else if(b<c)
{
Tracing[i][j]=3;//Means Delete
return b;
}
else
{
Tracing[i][j]=4;//Means Add
return c;
}
}
void printChanges(int i,int j)
{
if ( (i==0&& j==0) || (i<0 || j<0) ) return;
if(Tracing[i][j]==1)//Means Copy
{
printChanges(i-1,j-1);
}
else if (Tracing[i][j]==2)//Means Replace
{
printChanges(i-1,j-1);
cout<<"C"<<SecondString[i-1];
if(j+NoOfAdditions-NoOfDeletions<10)
cout<<"0";
cout<<j+NoOfAdditions-NoOfDeletions;
}
else if (Tracing[i][j]==3)//Means Delete
{
printChanges(i,j-1); NoOfDeletions++;
cout<<"D"<<FirstString[j-1];
if(j+NoOfAdditions-NoOfDeletions<10)
cout<<"0";
cout<<j+NoOfAdditions-NoOfDeletions+1;
}
else if (Tracing[i][j]==4)//Means Add
{
printChanges(i-1,j); NoOfAdditions++;
cout<<"I"<<SecondString[i-1];
if(j+NoOfAdditions-NoOfDeletions<10)
cout<<"0";
cout<<j+NoOfAdditions-NoOfDeletions;
}
}
int main()
{
cin>>FirstString>>SecondString;
while (FirstString!="#")
{
NoOfDeletions=0;
NoOfAdditions=0;
int Operation1,Operation2,Operation3;
int LengthOfFirstString=FirstString.length();
int LengthOfSecondString=SecondString.length();
EditDistance[0][0]=0;
for(int i=1;i<=LengthOfSecondString;i++)
{
EditDistance[i][0]=EditDistance[i-1][0]+1;
Tracing[i][0]=4;
}
for(int i=1;i<=LengthOfFirstString;i++)
{
EditDistance[0][i]=EditDistance[0][i-1]+1;
Tracing[0][i]=3;
}
for(int i=1;i<=LengthOfFirstString;i++)
{
for(int j=1;j<=LengthOfSecondString;j++)
{
if(FirstString[i-1]==SecondString[j-1])//compare two letters
{
EditDistance[j][i]=EditDistance[j-1][i-1];
Tracing[j][i]=1;
//this when the two letters are equal
//tracing [i][j]=1 means that we have copied the letter and not making any changes
}
else
{
Operation1=EditDistance[j-1][i-1]+1;//replace
Operation3=EditDistance[j-1][i]+1;//add
Operation2=EditDistance[j][i-1]+1;//delete
EditDistance[j][i]=FindMin(Operation1,Operation2,Operation3,j,i);
//get the min distance
//Operation 1 :replace d
//Operation 2 :delete
//Operation 3 :add
}
}
}
printChanges(LengthOfSecondString,LengthOfFirstString);//this function is a recursive function that print exactly the changes
cout<<"E"<<endl;//means finito (we have finished from changing string 1 to string 2)
//cout<<EditDistance[LengthOfSecondString][LengthOfFirstString];
cin>>FirstString>>SecondString;
}
}