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;
	}




}

I tried to read your code to understand your algorithm, but I didn't recognize it, and the limited commenting you provided didn't make it much clearer.

If you run the program with the sample from the link, do you get the same output?

What other test data did you provide to the program?

Did it appear to produce the correct output?

For the input line "apple bagpipe" the process should be something like this:
Ib01 (bapple)
Cg03 (bagple)
Ci05 (bagpie)
Ip06 (bagpipe)
So the output should be:
Ib01Cg03Ci05Ip06E

Or is this more minimal?
Ib01 (bapple)
Ig03 (bagpple)
Ii05 (bagpiple)
Dl07 (bagpipe)
Ib01Ig03Ii05Dl07E

What output does your program produce?

I tried to read your code to understand your algorithm, but I didn't recognize it, and the limited commenting you provided didn't make it much clearer.

If you run the program with the sample from the link, do you get the same output?

What other test data did you provide to the program?

Did it appear to produce the correct output?

For the input line "apple bagpipe" the process should be something like this:
Ib01 (bapple)
Cg03 (bagple)
Ci05 (bagpie)
Ip06 (bagpipe)
So the output should be:
Ib01Cg03Ci05Ip06E

Or is this more minimal?
Ib01 (bapple)
Ig03 (bagpple)
Ii05 (bagpiple)
Dl07 (bagpipe)
Ib01Ig03Ii05Dl07E

What output does your program produce?

thanks so so much i get accepted the problem was in the printchanges function
ur help is so appreciated

This article has been dead for over six months. Start a new discussion instead.