## 164 - String Computer

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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.
If only I had as much free time as I did in college...
tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there
Thank you very much..
I completley forgot that comparation and concetation of strings don't take O(1) time.
A stupid mistake.
If I am out of my mind, it's all right with me.
worm3959
New poster
Posts: 4
Joined: Tue Nov 29, 2005 5:49 am
Contact:

### Misadventure

Maxim wrote: I'm not total newbie to DP as I seem to be.
Well that was a bit messed up... 8)
sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

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

Code: Select all

``````#include <fstream.h>
#include <string.h>
char a,b;
int d,p,lena,lenb;
int x, y, 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]=i;
p[i]=3;
}
for(i=0;i<=lena;i++){
d[i]=i;
p[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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

### 164 HELP!! ME [WA]

Code: Select all

``````#include <fstream.h>
#include <string.h>
char a,b;
int d,p,lena,lenb;
int x, y, 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]=i;
p[i]=3;
}
for(i=0;i<=lena;i++){
d[i]=i;
p[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
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

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

Code: Select all

``````#include <fstream.h>
#include <string.h>
char a,b;
int d,p,lena,lenb;
int x, y, 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]=i;
p[i]=3;
}
for(i=0;i<=lena;i++){
d[i]=i;
p[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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### 164 String Computer,WA

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]=i;
b[i]=3;
}
for(j=1 ; j<=c ; j++){
d[j]=j;
b[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();
}
}
``````
Narek Saribekyan
snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### Look Here!

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;
for(i=1 ; i<=r ; i++){
d[i]=i;
b[i]=3;
}
for(j=1 ; j<=c ; j++){
d[j]=j;
b[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();
}``````
Narek Saribekyan
yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

### 164 i can't understand .. why WA

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, s;
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 = i;s=1;}
for(i=1;i<=ta;i++){d = i;s=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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### Oders in problem 164(String Computer)

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?
Narek Saribekyan
sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

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

Code: Select all

``````#include <fstream.h>
#include <string.h>
char a,b;
int d,p,lena,lenb;
int x, y, 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]=i;
p[i]=3;
}
for(i=0;i<=lena;i++){
d[i]=i;
p[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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### 164 - WA

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;
for(i=1 ; i<=r ; i++){
d[i]=i;
b[i]=3;
}
for(j=1 ; j<=c ; j++){
d[j]=j;
b[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
Narek Saribekyan
LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

### 164 WA

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 != '#')
{
int i, j;

x = string(" ") + x;
y = string(" ") + y;
int D = { 0 };
int DS = { 0 };
int a = x.length(), b = y.length();

for (i=0; i<=a; i++)
D[i] = i;
for (i=0; i<=b; i++)
D[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] = i;
for (i=0; i<=b; i++)
D[i] = i; ``````
can anyone explain this?
- Chris Adams
LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:
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;
}
}``````
- Chris Adams