164 - String Computer

Abednego · Post by **Abednego** » Tue Nov 01, 2005 7:46 pm

Your solution takes C*n^3 time, where C is a very large constant. Instead of working with a matrix of strings, try to convert it to a matrix of integers and then rebuild the string at the very end. Then you will have an n^2 algorithm.

tRipper · Post by **tRipper** » Tue Nov 01, 2005 7:56 pm

Thank you very much..
I completley forgot that comparation and concetation of strings don't take O(1) time.
A stupid mistake.

worm3959 · Post by **worm3959** » Tue Nov 29, 2005 5:57 am

Maxim wrote: I'm not total newbie to DP as I seem to be.

Well that was a bit messed up...

8)

sds1100 · Post by **sds1100** » Thu Dec 15, 2005 3:57 am

Code: Select all

#include <fstream.h> 
#include <string.h> 
char a[1000],b[1000]; 
int d[1000][1000],p[1000][1000],lena,lenb; 
int x[1000], y[1000], cnt; 
int delta; 

void main() 
{ 
   int i,j, k = 0; 
   while(1){ 
      cin >> a; 
      if(strcmp(a,"#")==0)break; 
      cin >> b; 
//      if (k == 1) cout << endl; 
      lena=strlen(a); 
      lenb=strlen(b); 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            d[i][j]=0; 
            p[i][j]=0; 
         } 
      } 
      for(i=0;i<=lenb;i++){ 
         d[i][0]=i; 
         p[i][0]=3; 
      } 
      for(i=0;i<=lena;i++){ 
         d[0][i]=i; 
         p[0][i]=4; 
      } 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            if(d[i][j]>=d[i-1][j]+1){ 
               d[i][j]=d[i-1][j]+1; 
               p[i][j]=3; 
            } 
            //if(d[i][j]>=d[i][j-1]+1){ 
               d[i][j]=d[i][j-1]+1; 
               p[i][j]=4; 
            //} 
            if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){ 
               d[i][j]=d[i-1][j-1]; 
               p[i][j]=1; 
            } 
            else if (d[i][j] >= d[i-1][j-1]+1){ 
               d[i][j]=d[i-1][j-1]+1; 
               p[i][j]=2; 
            } 
         } 
      } 
      cout << d[lenb][lena] << endl; 
      delta = 0; 
      cnt = 0; 
      i = lenb; 
      j = lena; 
      while (i != 0 || j != 0) { 
         switch(p[i][j]) { 
         case 2: x[cnt] = j; y[cnt++] = i; 
         case 1: --i; --j; break; 
         case 3: x[cnt] = j; y[cnt++] = i; --i; break; 
         case 4: x[cnt] = j; y[cnt++] = i; --j; break; 
         } 
      } 
       
      for (i = cnt-1; i >= 0; i--) { 
         switch(p[y[i]][x[i]]){ 
            case 2: 
               cout << "C" << b[y[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta; 
               } 
               else{ 
                  cout << x[i]+delta; 
               } 
            break; 
            case 3: 
               cout << "I" << b[y[i]-1]; 
               if(x[i]+1+delta<10){ 
                  cout << "0" << x[i]+1+delta++; 
               } 
               else{ 
                  cout  << x[i]+1+delta++; 
               } 
            break; 
            case 4: 
               cout << "D" << a[x[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta--; 
               } 
               else{ 
                  cout << x[i]+delta--; 
               } 
            break; 
         } 
      }    
      if(d[lenb][lena]!=0)cout << "E" << endl; 
      //if (k == 0) k++; 
   } 
}

I got Ac 526
Help me...

chunyi81 · Post by **chunyi81** » Thu Dec 15, 2005 4:44 am

Did you read this thread?

http://online-judge.uva.es/board/viewtopic.php?t=1526

sds1100 · Post by **sds1100** » Sat Dec 17, 2005 1:42 pm

Code: Select all

#include <fstream.h> 
#include <string.h> 
char a[1000],b[1000]; 
int d[1000][1000],p[1000][1000],lena,lenb; 
int x[1000], y[1000], cnt; 
int delta; 

void main() 
{ 
   int i,j, k = 0; 
   while(1){ 
      cin >> a; 
      if(strcmp(a,"#")==0)break; 
      cin >> b; 
//      if (k == 1) cout << endl; 
      lena=strlen(a); 
      lenb=strlen(b); 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            d[i][j]=0; 
            p[i][j]=0; 
         } 
      } 
      for(i=0;i<=lenb;i++){ 
         d[i][0]=i; 
         p[i][0]=3; 
      } 
      for(i=0;i<=lena;i++){ 
         d[0][i]=i; 
         p[0][i]=4; 
      } 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            if(d[i][j]>=d[i-1][j]+1){ 
               d[i][j]=d[i-1][j]+1; 
               p[i][j]=3; 
            } 
            //if(d[i][j]>=d[i][j-1]+1){ 
               d[i][j]=d[i][j-1]+1; 
               p[i][j]=4; 
            //} 
            if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){ 
               d[i][j]=d[i-1][j-1]; 
               p[i][j]=1; 
            } 
            else if (d[i][j] >= d[i-1][j-1]+1){ 
               d[i][j]=d[i-1][j-1]+1; 
               p[i][j]=2; 
            } 
         } 
      } 
      cout << d[lenb][lena] << endl; 
      delta = 0; 
      cnt = 0; 
      i = lenb; 
      j = lena; 
      while (i != 0 || j != 0) { 
         switch(p[i][j]) { 
         case 2: x[cnt] = j; y[cnt++] = i; 
         case 1: --i; --j; break; 
         case 3: x[cnt] = j; y[cnt++] = i; --i; break; 
         case 4: x[cnt] = j; y[cnt++] = i; --j; break; 
         } 
      } 
        
      for (i = cnt-1; i >= 0; i--) { 
         switch(p[y[i]][x[i]]){ 
            case 2: 
               cout << "C" << b[y[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta; 
               } 
               else{ 
                  cout << x[i]+delta; 
               } 
            break; 
            case 3: 
               cout << "I" << b[y[i]-1]; 
               if(x[i]+1+delta<10){ 
                  cout << "0" << x[i]+1+delta++; 
               } 
               else{ 
                  cout  << x[i]+1+delta++; 
               } 
            break; 
            case 4: 
               cout << "D" << a[x[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta--; 
               } 
               else{ 
                  cout << x[i]+delta--; 
               } 
            break; 
         } 
      }    
      if(d[lenb][lena]!=0)cout << "E" << endl; 
      //if (k == 0) k++; 
   } 
}

WHY WA

HELP ME

sds1100 · Post by **sds1100** » Mon Jan 16, 2006 12:49 pm

Code: Select all

#include <fstream.h> 
#include <string.h> 
char a[1000],b[1000]; 
int d[1000][1000],p[1000][1000],lena,lenb; 
int x[1000], y[1000], cnt; 
int delta; 

void main() 
{ 
   int i,j, k = 0; 
   while(1){ 
      cin >> a; 
      if(strcmp(a,"#")==0)break; 
      cin >> b; 
//      if (k == 1) cout << endl; 
      lena=strlen(a); 
      lenb=strlen(b); 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            d[i][j]=0; 
            p[i][j]=0; 
         } 
      } 
      for(i=0;i<=lenb;i++){ 
         d[i][0]=i; 
         p[i][0]=3; 
      } 
      for(i=0;i<=lena;i++){ 
         d[0][i]=i; 
         p[0][i]=4; 
      } 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            if(d[i][j]>=d[i-1][j]+1){ 
               d[i][j]=d[i-1][j]+1; 
               p[i][j]=3; 
            } 
            //if(d[i][j]>=d[i][j-1]+1){ 
               d[i][j]=d[i][j-1]+1; 
               p[i][j]=4; 
            //} 
            if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){ 
               d[i][j]=d[i-1][j-1]; 
               p[i][j]=1; 
            } 
            else if (d[i][j] >= d[i-1][j-1]+1){ 
               d[i][j]=d[i-1][j-1]+1; 
               p[i][j]=2; 
            } 
         } 
      } 
      cout << d[lenb][lena] << endl; 
      delta = 0; 
      cnt = 0; 
      i = lenb; 
      j = lena; 
      while (i != 0 || j != 0) { 
         switch(p[i][j]) { 
         case 2: x[cnt] = j; y[cnt++] = i; 
         case 1: --i; --j; break; 
         case 3: x[cnt] = j; y[cnt++] = i; --i; break; 
         case 4: x[cnt] = j; y[cnt++] = i; --j; break; 
         } 
      } 
        
      for (i = cnt-1; i >= 0; i--) { 
         switch(p[y[i]][x[i]]){ 
            case 2: 
               cout << "C" << b[y[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta; 
               } 
               else{ 
                  cout << x[i]+delta; 
               } 
            break; 
            case 3: 
               cout << "I" << b[y[i]-1]; 
               if(x[i]+1+delta<10){ 
                  cout << "0" << x[i]+1+delta++; 
               } 
               else{ 
                  cout  << x[i]+1+delta++; 
               } 
            break; 
            case 4: 
               cout << "D" << a[x[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta--; 
               } 
               else{ 
                  cout << x[i]+delta--; 
               } 
            break; 
         } 
      }    
      if(d[lenb][lena]!=0)cout << "E" << endl; 
      //if (k == 0) k++; 
   } 
}

why WA!!
T_T

PLEASE HELP ME..

snar · Post by **snar** » Mon Jan 16, 2006 3:41 pm

Can anybody say why I am getting WA?
I'm using Edit(Levenshtein) Distance method and then I'm tracing back using recursion. Maybe I've mistaken in taking array of positions. Every time when I'm deleting or inserting new character I'm changing elements in array "pos" (elements that are righter than position of deletion or insertion). Isn't that true?
Here is my code below.

Code: Select all

// 164 String Computer - Edit (Levenshtein) Distance - Dynamic Programming

#include <stdio.h>
#include <string.h>

// the maximum length of strings
#define MAX 22 

int d[MAX][MAX],b[MAX][MAX],pos[MAX],r,c,k;
char s[MAX], t[MAX];

// tracing back using recursive function 
void print(int i, int j){
    if (i==0&&j==0) return;
    if (b[i][j]==1){
        print(i,j-1);
		if (pos[i-1] < 10) 
			printf("I%c0%d",t[j-1],pos[i-1]+1); 
		else
            printf("I%c%d",t[j-1],pos[i-1]+1);
        for (k=i; k<r; k++)	pos[k]++;
    }
	else if (b[i][j]==2){
		print(i-1,j-1);
		if (d[i][j]!=d[i-1][j-1])
			if (pos[i-1] < 10) 
				printf("C%c0%d",t[j-1],pos[i-1]); 
			else
				printf("C%c%d",t[j-1],pos[i-1]);			
	}
	else
    {
		print(i-1,j);
		if (pos[i-1] < 10) 
			printf("D%c0%d",s[i-1],pos[i-1]); 
		else
            printf("D%c%d",s[i-1],pos[i-1]);
		for (k=i; k<r; k++)	pos[k]--;
	}	
}
// LevenshteinDistance function
int LevenshteinDistance(){
	int cost,i,j;
   	r = strlen(s);
	c = strlen(t);
	for(i=0 ; i<=r ; i++){
		d[i][0]=i;
		b[i][0]=3;
	}
	for(j=1 ; j<=c ; j++){
		d[0][j]=j;
		b[0][j]=1;
	}
	for(i=1 ; i<=r ; i++)
		for(j=1 ; j<=c ; j++)
		{
			cost = (s[i-1]==t[j-1]) ? 0 : 1;
			if (d[i][j-1]<=d[i-1][j] && d[i][j-1]+1<=d[i-1][j-1]+cost){
				d[i][j] = d[i][j-1]+1;
				b[i][j] = 1;				
			} else if (d[i-1][j-1]+cost<=d[i-1][j]){
                d[i][j] = d[i-1][j-1]+cost;
				b[i][j] = 2;
			}else
			{
				d[i][j] = d[i-1][j]+1;
				b[i][j] = 3;
			}
		}
	for (i=0; i<r; i++) pos[i]=i+1;
	print(r, c);
	printf("E\n");	
	return d[r][c];
}
void main()
{
	char ln[MAX];
	int i,j;
	while (gets(ln), strcmp(ln, "#"))
	{		
		i=0;
		j=0;
        while (ln[i] && ln[i] != ' ')
			s[j++] = ln[i++];
		s[j]='\0';
		while (ln[i] && ln[i] == ' ') 
			i++;
		j=0;
		while (ln[i])
			t[j++] = ln[i++];
		t[j]='\0';
		LevenshteinDistance();		
	}
}

snar · Post by **snar** » Mon Jan 16, 2006 8:16 pm

I got accepted for problem 526 which is very familiar to this one. Anyway, I'm still getting WA for this problem. I fixed my mistakes in code above and wrote it just like problem 526(with some changes in output).

"yiuyuho" wrote

This is strange:

I calculated the distance and back track:
I track for IDC and I got WA, but when I track in the order DIC I get AC, then I discover:

IDC, DCI, CID --> WA
DIC, ICD, CDI --> AC

The procedures of tracking is exactly identical, only the if-statements order is altered, how can that alter the outcome?

It there something wrong with the judge?

I tried this too, but I'm still getting WA. I would like to know, is there anyone that haven't took care about empty strings and got AC?.

Anyway, I tried the trick with empty strings too, but that didn't help.
So I can't understand were I made a mistake (or there is something incorrect at the judge)
Is there anyone that can look at my code and help me?

Code: Select all

// 164 String Computer - Edit (Levenshtein) Distance - Dynamic Programming

#include <stdio.h>
#include <string.h>

// the maximum length of strings
#define MAX 22
#define min(a, b)  (((a) < (b)) ? (a) : (b))

int d[MAX][MAX],b[MAX][MAX],pos[MAX],r,c,k;
char s[MAX], t[MAX];

// tracing back using recursive function 
void print(int i, int j){
    if (i==0&&j==0) return;
    if (b[i][j]==1){
        print(i,j-1);
		if (pos[i-1] < 10) 
			printf("I%c0%d",t[j-1],pos[i]+1); 
		else
            printf("I%c%d",t[j-1],pos[i]+1);
        for (k=i; k<=r; k++)	pos[k]++;
    }
	else if (b[i][j]==2){
		print(i-1,j-1);
		if (d[i][j]!=d[i-1][j-1])
			if (pos[i-1] < 10) 
				printf("C%c0%d",t[j-1],pos[i]); 
			else
				printf("C%c%d",t[j-1],pos[i]);			
	}
	else
    {
		print(i-1,j);
		if (pos[i-1] < 10) 
			printf("D%c0%d",s[i-1],pos[i]); 
		else
            printf("D%c%d",s[i-1],pos[i]);
		for (k=i; k<=r; k++)	pos[k]--;
	}	
}
// LevenshteinDistance function
int LevenshteinDistance(){
	int cost,i,j;
   	r = strlen(s);
	c = strlen(t);
	d[0][0]=0;
	for(i=1 ; i<=r ; i++){
		d[i][0]=i;
		b[i][0]=3;
	}
	for(j=1 ; j<=c ; j++){
		d[0][j]=j;
		b[0][j]=1;
	}
	for(i=1 ; i<=r ; i++)
		for(j=1 ; j<=c ; j++)
		{
			cost = (s[i-1]==t[j-1]) ? 0 : 1;
			d[i][j] = min(d[i-1][j-1]+cost,min(d[i-1][j]+1,d[i][j-1]+1));
			if (d[i][j]==d[i][j-1]+1)
				b[i][j] = 1;
			else if (d[i][j]==d[i-1][j-1]+cost)
				b[i][j] = 2;
			else
				b[i][j] = 3;
		}
	for (i=0; i<=r; i++) pos[i]=i;
	print(r, c);
	printf("E\n");	
	return d[r][c];
}
void main()
{
	while (scanf("%s",s) && strcmp(s,"#") && scanf("%s",t)) LevenshteinDistance();		
}

yolongyi · Post by **yolongyi** » Mon Jan 16, 2006 9:27 pm

i'm getting WA....
i can't understand...

i try already IDC,ICD ...all of cases.. and i can't get AC..
what is wrong in my source...

is there any special case like blank line??
plz help me...

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>

using namespace std;

void main(){
int in, ta, i, j, cost, min;
string input, target, str;
int d[100][100], s[100][100];
vector < pair<int,int> > v;

getline(cin,str);
while(str.compare("#")!=0){
input = str.substr(0,str.find(' '));
target = str.substr(str.find(' ') + 1, str.length());

in = input.length();
ta = target.length();
v.clear();

if(in==0) for(i=0;i<ta;i++) printf("I%c%02d",target,i+1);
else if(ta==0) for(i=0;i<in;i++) printf("D%c%02d",input,1);
else{
for(i=0;i<=in;i++){d[0] = i;s[0]=1;}
for(i=1;i<=ta;i++){d[0] = i;s[0]=0;}

for(j=1;j<=in;j++){
for(i=1;i<=ta;i++){
if(input[j-1]==target[i-1]) cost = 0;
else cost = 1;
min = 999999;

if(min > d[j-1] + 1){
min = d[j-1] + 1;
s[j] = 1;
}
if(min > d[i-1][j] + 1){
min = d[i-1][j] + 1;
s[j] = 0;
}
if(min > d[i-1][j-1] + cost){
min = d[i-1][j-1] + cost;
s[i][j] = 2;
}

d[i][j] = min;
}
}
while(!(in==0 && ta==0)){
v.push_back(pair<int,int>(ta,in));
if(s[ta][in]==0) ta--;
else if(s[ta][in]==1) in--;
else if(s[ta][in]==2) {ta--;in--;}
}
v.push_back(pair<int,int>(0,0));
for(i=v.size()-1;i>0;i--){
if(d[v[i-1].first][v[i-1].second]!=d[v[i].first][v[i].second]){
if(s[v[i-1].first][v[i-1].second]==0){
printf("I%c%02d",target[v[i-1].first-1],v[i-1].first);
}
else if(s[v[i-1].first][v[i-1].second]==1){
printf("D%c%02d",input[v[i-1].second-1],v[i-1].second);
}
else{
printf("C%c%02d",target[v[i-1].first-1],v[i-1].first);
}
}
}
}
cout<<"E"<<endl;
getline(cin,str);
}
}

snar · Post by **snar** » Tue Jan 17, 2006 11:59 am

There was a topic about this problem that there is a wrong judge and it's possible to get WA in some cases. I tried to control orders (for example like DIC). That means, if you have more that one choice, you must first do Delete then Insert and finally Change, right?.
I'm not sure about doing all this, so I would like to know your opinion about my method.
So, what I'm doing?
I'm taking two 2-dimensional arrays("d and "b"). "d" for minimal distances and "b"-for tracing back(parent information).

b[j] == 1 <=> INSERT;
b[j] == 2 <=> CHANGE;
b[j] == 3 <=> DELETE;

Code: Select all

for(i=1 ; i<=r ; i++)
		for(j=1 ; j<=c ; j++)
		{
			cost = (s[i-1]==t[j-1]) ? 0 : 1;
			d[i][j] = min(d[i-1][j-1]+cost,d[i-1][j]+1,d[i][j-1]+1);
			if (d[i][j]==d[i][j-1]+1)// Insert
				b[i][j] = 1;
			else if (d[i][j]==d[i-1][j-1]+cost)// Change
				b[i][j] = 2;
			else// Delete
				b[i][j] = 3;
		}

I can change priority using this method. In the sample above I wrote orders for ICD. So, If I want to change it to DIC, I can wrote like this.

Code: Select all

if (d[i][j]==d[i-1][j]+1)// Delete
				b[i][j] = 3;
			else if (d[i][j]==d[i][j-1]+1)// Insert
				b[i][j] = 1;
			else// Change
				b[i][j] = 2;

After that I'm tracing back using recursice function.

Code: Select all

void print(int i, int j){
    if (i==0&&j==0) return;
    if (b[i][j]==1){
        print(i,j-1);
		if (pos[i-1] < 10) 
			printf("I%c0%d",t[j-1],pos[i]+1); 
		else
            printf("I%c%d",t[j-1],pos[i]+1);
        for (k=i; k<=r; k++)	pos[k]++;
    }
	else if (b[i][j]==2){
		print(i-1,j-1);
		if (d[i][j]!=d[i-1][j-1])
			if (pos[i-1] < 10) 
				printf("C%c0%d",t[j-1],pos[i]); 
			else
				printf("C%c%d",t[j-1],pos[i]);			
	}
	else
    {
		print(i-1,j);
		if (pos[i-1] < 10) 
			printf("D%c0%d",s[i-1],pos[i]); 
		else
            printf("D%c%d",s[i-1],pos[i]);
		for (k=i; k<=r; k++)	pos[k]--;
	}	
}

I tried all possible combinations, but that didn't help.
What do you think? Does this seem to be a correct solution?

sds1100 · Post by **sds1100** » Mon Jan 30, 2006 8:25 am

Code: Select all

#include <fstream.h> 
#include <string.h> 
char a[1000],b[1000]; 
int d[1000][1000],p[1000][1000],lena,lenb; 
int x[1000], y[1000], cnt; 
int delta; 

void main() 
{ 
   int i,j, k = 0; 
   while(1){ 
      cin >> a; 
      if(strcmp(a,"#")==0)break; 
      cin >> b; 
//      if (k == 1) cout << endl; 
      lena=strlen(a); 
      lenb=strlen(b); 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            d[i][j]=0; 
            p[i][j]=0; 
         } 
      } 
      for(i=0;i<=lenb;i++){ 
         d[i][0]=i; 
         p[i][0]=3; 
      } 
      for(i=0;i<=lena;i++){ 
         d[0][i]=i; 
         p[0][i]=4; 
      } 
      for(i=1;i<=lenb;i++){ 
         for(j=1;j<=lena;j++){ 
            if(d[i][j]>=d[i-1][j]+1){ 
               d[i][j]=d[i-1][j]+1; 
               p[i][j]=3; 
            } 
            //if(d[i][j]>=d[i][j-1]+1){ 
               d[i][j]=d[i][j-1]+1; 
               p[i][j]=4; 
            //} 
            if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){ 
               d[i][j]=d[i-1][j-1]; 
               p[i][j]=1; 
            } 
            else if (d[i][j] >= d[i-1][j-1]+1){ 
               d[i][j]=d[i-1][j-1]+1; 
               p[i][j]=2; 
            } 
         } 
      } 
      cout << d[lenb][lena] << endl; 
      delta = 0; 
      cnt = 0; 
      i = lenb; 
      j = lena; 
      while (i != 0 || j != 0) { 
         switch(p[i][j]) { 
         case 2: x[cnt] = j; y[cnt++] = i; 
         case 1: --i; --j; break; 
         case 3: x[cnt] = j; y[cnt++] = i; --i; break; 
         case 4: x[cnt] = j; y[cnt++] = i; --j; break; 
         } 
      } 
        
      for (i = cnt-1; i >= 0; i--) { 
         switch(p[y[i]][x[i]]){ 
            case 2: 
               cout << "C" << b[y[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta; 
               } 
               else{ 
                  cout << x[i]+delta; 
               } 
            break; 
            case 3: 
               cout << "I" << b[y[i]-1]; 
               if(x[i]+1+delta<10){ 
                  cout << "0" << x[i]+1+delta++; 
               } 
               else{ 
                  cout  << x[i]+1+delta++; 
               } 
            break; 
            case 4: 
               cout << "D" << a[x[i]-1]; 
               if(x[i]+delta<10){ 
                  cout << "0" << x[i]+delta--; 
               } 
               else{ 
                  cout << x[i]+delta--; 
               } 
            break; 
         } 
      }    
      if(d[lenb][lena]!=0)cout << "E" << endl; 
      //if (k == 0) k++; 
   } 
}

HELP ME!!

snar · Post by **snar** » Sun Apr 02, 2006 7:27 pm

Hello,
I have watched the whole forum for help to solve this problem. I have fixed my code many times but that didn't help - I'm getting WA again and again.

Anybody? I need help.
Note that I have solved the problem 526 and my problem is (OJ's problem) which one of solutions to print out when there is more than one solutions.
And please, do not link me to another topic - I have travelled trought all topics in this forum. Just take a moment to look at my code, please.
I think you'll understand it momentary if you have solved this problem.

Code: Select all

// 164 String Computer - Edit (Levenshtein) Distance - Dynamic Programming

#include <stdio.h>
#include <string.h>

// the maximum length of strings
#define MAX 22
#define min(a, b)  (((a) < (b)) ? (a) : (b))

int d[MAX][MAX],b[MAX][MAX],pos[MAX],r,c,k;
char s[MAX], t[MAX];

// tracing back using recursive function 
void print(int i, int j){
    if (i==0&&j==0) return;
    if (b[i][j]==1){
        print(i,j-1);
		if (pos[i-1] < 10) 
			printf("I%c0%d",t[j-1],pos[i]+1); 
		else
            printf("I%c%d",t[j-1],pos[i]+1);
        for (k=i; k<=r; k++)	pos[k]++;
    }
	else if (b[i][j]==2){
		print(i-1,j-1);
		if (d[i][j]!=d[i-1][j-1])
			if (pos[i-1] < 10) 
				printf("C%c0%d",t[j-1],pos[i]); 
			else
				printf("C%c%d",t[j-1],pos[i]);			
	}
	else
    {
		print(i-1,j);
		if (pos[i-1] < 10) 
			printf("D%c0%d",s[i-1],pos[i]); 
		else
            printf("D%c%d",s[i-1],pos[i]);
		for (k=i; k<=r; k++)	pos[k]--;
	}	
}
// LevenshteinDistance function
int LevenshteinDistance(){
	int cost,i,j;
   	r = strlen(s);
	c = strlen(t);
	d[0][0]=0;
	for(i=1 ; i<=r ; i++){
		d[i][0]=i;
		b[i][0]=3;
	}
	for(j=1 ; j<=c ; j++){
		d[0][j]=j;
		b[0][j]=1;
	}
	for(i=1 ; i<=r ; i++)
		for(j=1 ; j<=c ; j++)
		{
			cost = (s[i-1]==t[j-1]) ? 0 : 1;
			d[i][j] = min(d[i-1][j-1]+cost,min(d[i-1][j]+1,d[i][j-1]+1));
			if (d[i][j]==d[i][j-1]+1)
				b[i][j] = 1;
			else if (d[i][j]==d[i-1][j-1]+cost)
				b[i][j] = 2;
			else
				b[i][j] = 3;
		}
	for (i=0; i<=r; i++) pos[i]=i;
	print(r, c);
	printf("E\n");	
	return d[r][c];
}
void main()
{
	while (scanf("%s",s) && strcmp(s,"#") && scanf("%s",t)) LevenshteinDistance();		
}

Thanks in advance

LithiumDex · Post by **LithiumDex** » Sun Aug 27, 2006 8:37 pm

I have tested my solution with many inputs, and cannot find a problem. Although my outputs are very different from most of the ones I found, they all contained the correct Levenstien Distance # of commands, and when I went through those commands, they all turned x into y.

Here is my source code:

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string makeindex ( int n )
{
    return string("") + (char)('0' + (n/10)) + string("")+
           (char)('0' + (n%10));
}

int main ( void )
{
    string x, y;

    while ((cin >> x >> y) && x[0] != '#')
    {
        int i, j;
      
        x = string(" ") + x;
        y = string(" ") + y;
        int D[22][22] = { 0 };
        int DS[22][22] = { 0 };
        int a = x.length(), b = y.length();

        for (i=0; i<=a; i++)
            D[i][0] = i;
        for (i=0; i<=b; i++)
            D[0][i] = i;

        for (i=1; i<=a; i++)
            for (j=1; j<=b; j++)
            {
                int cost = (x[i-1] == y[j-1]) ? 0 : 1;
                int cC = D[i-1][j-1] + cost;
                int cI = D[i][j-1] + 1;
                int cD = D[i-1][j] + 1;

                int m = min(min(cC, cI), cD);

                D[i][j] = m;
                              
                if (m == cI)
                   DS[i][j] = (2+(i<<8)+((j-1)<<16));
                else if (m == cC)
                    DS[i][j] = (1+((i-1)<<8)+((j-1)<<16));            
                else if (m == cD)
                    DS[i][j] = (3+((i-1)<<8)+(j<<16));
            }

        i = a; j = b;

        while (DS[i][j])
        {
            int xx = DS[i][j];
            int cmd = xx&0xff;
            int ni = (xx>>8)&0xff;
            int nj = xx>>16;

            if (x[ni] != y[nj])
            {
               if (cmd == 1)
                   cout << "C" << y[nj] << makeindex(ni);
               else if (cmd == 2)
                   cout << "I" << y[nj] << makeindex(ni);
               else if (cmd == 3)
                   cout << "D" << x[ni] << makeindex(ni);
            }
            
            i = ni; j = nj;
        }
        cout << "E" << endl;
    }

    return 0;
}

P.S:

I got the levenstien distance algo from wiki, and adapted it to give the commands, I understand it well -- accept for this code:

Code: Select all

for (i=0; i<=a; i++)
            D[i][0] = i;
        for (i=0; i<=b; i++)
            D[0][i] = i;

can anyone explain this?

LithiumDex · Post by **LithiumDex** » Mon Aug 28, 2006 4:01 am

AC by adding 9 characters of code too my solution.

I found my error after writing this small program to check output:

Code: Select all

#include <iostream>
#include <string>
using namespace std;

int main ( void )
{
    string x, y, cmd;
    
    while (cin >> x >> y >> cmd)
    {
        int len = (cmd.length()-1)/4;
        int i;

        for (i=0; i<(len*4); i+=4)
        {
            char c = cmd[i];
            char l = cmd[i+1];
            int in = (cmd[i+2]-'0')*10 + (cmd[i+3]-'0');
            
            if (c == 'C')
                x[in-1] = l;
            else if (c == 'I')
                x.insert(in-1, string("")+l);
            else if (c == 'D')
                x.erase(in-1, 1);
        }

        if (x != y) cout << "*";

        cout << x << " " << y << endl;
    }
}

OJ Board

164 - String Computer

Misadventure

HELP ME .. WA 164......?

164 HELP!! ME [WA]

164 Why WA!! Please Help me.. T_T Help me!!!!!!!!!!!!!!!!!!!

164 String Computer,WA

Look Here!

164 i can't understand .. why WA

Oders in problem 164(String Computer)

Please Help me!! ACM164 WA!!!!!!!!!!!

164 - WA

164 WA