## 526 - String Distance and Transform Process

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 526 String Editing

http://uva.onlinejudge.org/index.php?op ... category=7
You can see a yellow check next to 526, that means there is a special judge, and there are multiple correct outputs.

Your output is correct for sample input #2.
Check input and AC output for thousands of problems on uDebug!
mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 526 String Editing

empty string will be given as input.
i got AC after handling it.
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 526 String Editing

Getting WA...plzzz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
using namespace std;

typedef long long int L;
typedef unsigned long long int U;

int arr[85][85];
char op[85][85];
stack < pair<int,char> >st;
main()
{
char str1[85], str2[85];
int first = 1;
while(gets(str1))
{
gets(str2);
for(int i = 0;i<=strlen(str1);i++)
{
arr[0][i] = i;
op[0][i] = 'd';
}
for(int i = 0;i<=strlen(str2);i++)
{
arr[i][0] = i;
op[i][0] = 'i';
}
for(int i = 1;i<=strlen(str2);i++)
{
for(int j = 1;j<=strlen(str1);j++)
{
arr[i][j] = arr[i-1][j]+1;
op[i][j] = 'i';
if(arr[i][j-1]+1 < arr[i][j])
{
arr[i][j] = arr[i][j-1]+1;
op[i][j] = 'd';
}
if(arr[i-1][j-1] + (str2[i-1]!=str1[j-1]) < arr[i][j])
{
arr[i][j] = arr[i-1][j-1] + (str2[i-1]!=str1[j-1]);
op[i][j] = 'r';
}
//cout<<arr[i][j]<<op[i][j]<<" ";
}
//cout<<endl;
}
if(first)
first = 0;
else
printf("\n");
int x = strlen(str2);
int y = strlen(str1);
cout<<arr[x][y]<<endl;;
int c = 1;
while(arr[x][y])
{
int val = arr[x][y];
char oper = op[x][y];
if(op[x][y] == 'r')
{
x--;
y--;
}
else if(op[x][y] == 'i')
x--;
else
y--;
if(val > arr[x][y])
{
if(oper == 'i')
printf("%d Insert %d,%c\n",c++,min(x+2,y+1),str2[x]);
else if(oper == 'd')
printf("%d Delete %d\n", c++, y+1);
else
printf("%d Replace %d,%c\n",c++,y+1, str2[x]);
}
}
}
}
-@ce
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 526 String Editing

Try input:

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx
Your code is generating this string:

Code: Select all

vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphuthdqcpkhdnuvlgslx
Check input and AC output for thousands of problems on uDebug!
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 526 - String Distance and Transform Process

Input:

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx
AC output:

Code: Select all

57
1 Replace 58,x
2 Replace 57,l
3 Replace 56,s
4 Replace 55,g
5 Replace 54,l
6 Replace 53,v
7 Replace 52,u
8 Replace 51,n
9 Replace 50,d
10 Replace 48,k
11 Replace 47,p
12 Replace 46,c
13 Replace 45,q
14 Replace 44,d
15 Replace 43,h
16 Replace 42,t
17 Replace 41,o
18 Replace 40,h
19 Replace 39,p
20 Replace 38,w
21 Replace 37,g
22 Replace 36,u
23 Replace 35,f
24 Replace 34,r
25 Replace 33,h
26 Replace 32,c
27 Replace 31,z
28 Replace 30,d
29 Replace 29,v
30 Replace 28,b
31 Replace 27,q
32 Replace 26,y
33 Replace 25,v
34 Replace 24,m
35 Replace 23,w
36 Replace 22,s
37 Replace 20,b
38 Replace 19,m
39 Replace 18,d
40 Replace 17,t
41 Replace 16,m
42 Replace 15,t
43 Replace 14,v
44 Replace 13,n
45 Replace 12,a
46 Replace 11,b
47 Replace 10,s
48 Replace 9,b
49 Replace 8,v
50 Replace 7,r
51 Replace 6,m
52 Replace 5,l
53 Replace 4,d
54 Replace 3,s
55 Replace 2,d
56 Replace 1,f
57 Insert 1,v