526 - String Distance and Transform Process
Moderator: Board moderators
-
- New poster
- Posts: 28
- Joined: Mon Mar 01, 2004 11:29 pm
Why wrong?
I do this algorithm and I don
-
- New poster
- Posts: 28
- Joined: Mon Mar 01, 2004 11:29 pm
I got AC. My problem is with input. Have one space more in input.
Code: Select all
while(cin>>str1>>str2) // wrong
while(!cin.eof()) {
cin>>str1;
if (cin.eof()) break;
cin>>str2;
} // It is correct
-
- Experienced poster
- Posts: 105
- Joined: Wed May 25, 2005 7:23 am
Edit String 526 trace back operations
Hi,
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
-------code for only number of changes -------------------
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
Code: Select all
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
if (i == 0 || j == 0)
return;
if (final[i - 1][j] + 1 == final[i][j])
{
mytrace (i - 1, j):
printf ("insert \n");
}
else if (final[i][j - 1] + 1 == final[i][j])
{
mytrace (i, j - 1):
printf ("delete\n");
}
else
{
mytrace (i - 1, j - 1);
if (s[i - 1] != y[j - 1])
printf ("Replace\n");
}
return;
}
Code: Select all
#include<stdio.h>
int final[100][100];
char s[100], y[100];
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
return;
}
int
main ()
{
int len1, len2, i, j, val, p, q, r;
while (gets (s))
{
gets (y);
len1 = strlen (s);
len2 = strlen (y);
printf ("%s:%s\n", s, y);
for (i = 0; i <= len1 + 2; i++)
for (j = 0; j <= len2 + 2; j++)
{
final[i][j] = 0;
}
for (i = 0; i <= len1; i++)
final[i][0] = i;
for (j = 0; j <= len2; j++)
final[0][j] = j;
for (i = 1; i <= len1; i++)
for (j = 1; j <= len2; j++)
{
val = ((s[i - 1] == y[j - 1]) ? 0 : 1);
p = final[i - 1][j - 1] + val;
q = final[i][j - 1] + 1;
r = final[i - 1][j] + 1;
if (p <= q && p <= r)
{
final[i][j] = p;
}
else if (q <= p && q <= r)
{
final[i][j] = q;
}
else if (r <= p && r <= q)
{
final[i][j] = r;
}
}
printf ("%d\n", final[len1][len2]);
printf ("***************\n");
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
printf ("%d ", final[i][j]);
printf ("\n");
}
mytrace (len1, len2);
printf ("***************\n");
}
return 0;
}
Code: Select all
-
- Experienced poster
- Posts: 105
- Joined: Wed May 25, 2005 7:23 am
526 edit string trace back operations
Hi,
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
-------code for only number of changes -------------------
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
Code: Select all
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
if (i == 0 || j == 0)
return;
if (final[i - 1][j] + 1 == final[i][j])
{
mytrace (i - 1, j):
printf ("insert \n");
}
else if (final[i][j - 1] + 1 == final[i][j])
{
mytrace (i, j - 1):
printf ("delete\n");
}
else
{
mytrace (i - 1, j - 1);
if (s[i - 1] != y[j - 1])
printf ("Replace\n");
}
return;
}
Code: Select all
#include<stdio.h>
int final[100][100];
char s[100], y[100];
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
return;
}
int
main ()
{
int len1, len2, i, j, val, p, q, r;
while (gets (s))
{
gets (y);
len1 = strlen (s);
len2 = strlen (y);
printf ("%s:%s\n", s, y);
for (i = 0; i <= len1 + 2; i++)
for (j = 0; j <= len2 + 2; j++)
{
final[i][j] = 0;
}
for (i = 0; i <= len1; i++)
final[i][0] = i;
for (j = 0; j <= len2; j++)
final[0][j] = j;
for (i = 1; i <= len1; i++)
for (j = 1; j <= len2; j++)
{
val = ((s[i - 1] == y[j - 1]) ? 0 : 1);
p = final[i - 1][j - 1] + val;
q = final[i][j - 1] + 1;
r = final[i - 1][j] + 1;
if (p <= q && p <= r)
{
final[i][j] = p;
}
else if (q <= p && q <= r)
{
final[i][j] = q;
}
else if (r <= p && r <= q)
{
final[i][j] = r;
}
}
printf ("%d\n", final[len1][len2]);
printf ("***************\n");
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
printf ("%d ", final[i][j]);
printf ("\n");
}
mytrace (len1, len2);
printf ("***************\n");
}
return 0;
}
Code: Select all
-
- Experienced poster
- Posts: 105
- Joined: Wed May 25, 2005 7:23 am
edit string 526 traceback operations
Hi,
I should have posted this in C and C++
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
-------code for only number of changes -------------------
I should have posted this in C and C++
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
Code: Select all
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
if (i == 0 || j == 0)
return;
if (final[i - 1][j] + 1 == final[i][j])
{
mytrace (i - 1, j):
printf ("insert \n");
}
else if (final[i][j - 1] + 1 == final[i][j])
{
mytrace (i, j - 1):
printf ("delete\n");
}
else
{
mytrace (i - 1, j - 1);
if (s[i - 1] != y[j - 1])
printf ("Replace\n");
}
return;
}
Code: Select all
#include<stdio.h>
int final[100][100];
char s[100], y[100];
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
return;
}
int
main ()
{
int len1, len2, i, j, val, p, q, r;
while (gets (s))
{
gets (y);
len1 = strlen (s);
len2 = strlen (y);
printf ("%s:%s\n", s, y);
for (i = 0; i <= len1 + 2; i++)
for (j = 0; j <= len2 + 2; j++)
{
final[i][j] = 0;
}
for (i = 0; i <= len1; i++)
final[i][0] = i;
for (j = 0; j <= len2; j++)
final[0][j] = j;
for (i = 1; i <= len1; i++)
for (j = 1; j <= len2; j++)
{
val = ((s[i - 1] == y[j - 1]) ? 0 : 1);
p = final[i - 1][j - 1] + val;
q = final[i][j - 1] + 1;
r = final[i - 1][j] + 1;
if (p <= q && p <= r)
{
final[i][j] = p;
}
else if (q <= p && q <= r)
{
final[i][j] = q;
}
else if (r <= p && r <= q)
{
final[i][j] = r;
}
}
printf ("%d\n", final[len1][len2]);
printf ("***************\n");
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
printf ("%d ", final[i][j]);
printf ("\n");
}
mytrace (len1, len2);
printf ("***************\n");
}
return 0;
}
Code: Select all
-
- Experienced poster
- Posts: 105
- Joined: Wed May 25, 2005 7:23 am
edit string 526 traceback operations
Hi,
I should have posted this in C and C++
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
-------code for only number of changes -------------------
I should have posted this in C and C++
I have implemented the number of changes required for edit distance. I cannot trace back the number of changes like positions and insertions. I tried a lot but in vain.
The positions are also required. I am getting confused when there are insertions and deletions. Please do help.
False tries
Code: Select all
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
if (i == 0 || j == 0)
return;
if (final[i - 1][j] + 1 == final[i][j])
{
mytrace (i - 1, j):
printf ("insert \n");
}
else if (final[i][j - 1] + 1 == final[i][j])
{
mytrace (i, j - 1):
printf ("delete\n");
}
else
{
mytrace (i - 1, j - 1);
if (s[i - 1] != y[j - 1])
printf ("Replace\n");
}
return;
}
Code: Select all
#include<stdio.h>
int final[100][100];
char s[100], y[100];
void
mytrace (int i, int j)
{
/* Need this function so that it works for 526 */
return;
}
int
main ()
{
int len1, len2, i, j, val, p, q, r;
while (gets (s))
{
gets (y);
len1 = strlen (s);
len2 = strlen (y);
printf ("%s:%s\n", s, y);
for (i = 0; i <= len1 + 2; i++)
for (j = 0; j <= len2 + 2; j++)
{
final[i][j] = 0;
}
for (i = 0; i <= len1; i++)
final[i][0] = i;
for (j = 0; j <= len2; j++)
final[0][j] = j;
for (i = 1; i <= len1; i++)
for (j = 1; j <= len2; j++)
{
val = ((s[i - 1] == y[j - 1]) ? 0 : 1);
p = final[i - 1][j - 1] + val;
q = final[i][j - 1] + 1;
r = final[i - 1][j] + 1;
if (p <= q && p <= r)
{
final[i][j] = p;
}
else if (q <= p && q <= r)
{
final[i][j] = q;
}
else if (r <= p && r <= q)
{
final[i][j] = r;
}
}
printf ("%d\n", final[len1][len2]);
printf ("***************\n");
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
printf ("%d ", final[i][j]);
printf ("\n");
}
mytrace (len1, len2);
printf ("***************\n");
}
return 0;
}
Code: Select all
It is obvious, because you move in backward from your dynamic/memoization, so you can fill up your dynamic tables forward and go backward for showing the changes and make the wanted string.
I think this portion of my code helps you.
Code: Select all
void print(int a,int b)
{
switch(trace[a][b])
{
case 'g':
print(a-1,b-1);
return;
case 'c':
print(a-1,b-1);
str[a+temp-1]=s2[b-1];
cout<<++cc<<" Replace "<<a+temp<<','<<s2[b-1]<<endl;
return;
-
- New poster
- Posts: 3
- Joined: Mon Jun 05, 2006 4:44 am
- Location: Rio de Janeiro, Brasil
Even finding this kind of problem in some text books and using their code, I keep getting WA in this one.
I think I've checked the input correctly and the code seems ok with the one found in chapter 11 of Programming Challenges (it looks the same actually).
I've compared my output with the one posted by Caesum and it seems only the lines with Insert are different.
Could anyone, please, give some light to my thoughts!?
Thank you!
I think I've checked the input correctly and the code seems ok with the one found in chapter 11 of Programming Challenges (it looks the same actually).
I've compared my output with the one posted by Caesum and it seems only the lines with Insert are different.
Could anyone, please, give some light to my thoughts!?
Thank you!
Code: Select all
#include <stdio.h>
#include <string.h>
#define MATCH 0
#define INSERT 1
#define DELETE 2
#define MAXLEN 128
typedef struct {
int cost;
int parent;
} cell;
cell m[MAXLEN][MAXLEN];
int cmd;
void row_init (int i) {
m[0][i].cost = i;
if (i>0)
m[0][i].parent=INSERT;
else
m[0][i].parent=-1;
}
void column_init (int i) {
m[i][0].cost = i;
if (i>0)
m[i][0].parent=DELETE;
else
m[i][0].parent=-1;
}
int match (char c, char d) {
if (c==d) return 0;
return 1;
}
int string_compare (char *s, char *t) {
int sizes, sizet;
int i, j, k;
int opt[3];
for (i=0; i<MAXLEN; i++) {
row_init(i);
column_init(i);
}
sizes=strlen(s);
sizet=strlen(t);
for (i=1; i<sizes; i++)
for (j=1; j<sizet; j++) {
opt[MATCH] = m[i-1][j-1].cost + match(s[i], t[j]);
opt[INSERT] = m[i][j-1].cost + 1;
opt[DELETE] = m[i-1][j].cost + 1;
m[i][j].cost = opt[MATCH];
m[i][j].parent = MATCH;
for (k=INSERT; k<=DELETE; k++)
if (opt[k] < m[i][j].cost) {
m[i][j].cost = opt[k];
m[i][j].parent = k;
}
}
return m[sizes-1][sizet-1].cost;
}
void insert_out (char *t, int j) {
printf("%d Insert %d,%c\n", cmd++, j, t[j]);
}
void delete_out (char *s, int i) {
printf("%d Delete %d\n", cmd++, i);
}
void match_out (char *s, char *t, int i, int j) {
if (s[i]!=t[j])
printf("%d Replace %d,%c\n", cmd++, i, t[j]);
}
void reconstruct_path (char *s, char *t, int i, int j) {
if (m[i][j].parent == -1) return;
if (m[i][j].parent == MATCH) {
reconstruct_path(s, t, i-1, j-1);
match_out(s, t, i, j);
return;
}
if (m[i][j].parent == INSERT) {
reconstruct_path (s, t, i, j-1);
insert_out(t, j);
return;
}
if (m[i][j].parent == DELETE) {
reconstruct_path(s, t, i-1, j);
delete_out(s, i);
return;
}
}
int main (void) {
char s[MAXLEN], t[MAXLEN];
s[0]=t[0]=' ';
while (gets(&s[1])) {
gets(&t[1]);
printf("%d\n", string_compare (s, t));
cmd=1;
reconstruct_path(s, t, strlen(s)-1, strlen(t)-1);
printf("\n");
}
return 0;
}
I was getting WA on this problem until I realised the that it didn't say anywhere in the input that the strings weren't empty. I got AC after I made my program handle empty lines (and spaces). Here is some input and the output generated by my AC program.
Code: Select all
Input:
testing
a
b
Output:
7
1 Delete 7
2 Delete 6
3 Delete 5
4 Delete 4
5 Delete 3
6 Delete 2
7 Delete 1
1
1 Replace 1,b
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Hello everyone.
I am trying to solve this problem. I use String Distance Dynamic Programming algorithm. I fill DP array ok, but I have no idea on how to restore path. Can anyone help me with that??
Thanx.
I am trying to solve this problem. I use String Distance Dynamic Programming algorithm. I fill DP array ok, but I have no idea on how to restore path. Can anyone help me with that??
Thanx.
Now I lay me down to sleep...
my profile
my profile
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
how to restore path? depends on how your code is implemented. But i don't know how is your code.
normally path is showed recursively,,
for example in a graph
of 6 node
if there is a path 0->2-> 4-> 3-> 5
just store the previous node in the array..
and restore path recursively
_
It works like this:
hope it helps
normally path is showed recursively,,
for example in a graph
of 6 node
if there is a path 0->2-> 4-> 3-> 5
just store the previous node in the array..
and restore path recursively
_
Code: Select all
-------------------------------
0 1 2 3 4 5
-------------------------------
-1 -1 0 4 2 3
-------------------------------
Code: Select all
show(int n){
if(prev[n]!=-1)
show(prev[n]);
printf(" %d",n);
}
Code: Select all
show(5)
|
show(3) 5 // called show prev[5]=3 and prints 5
|
show(4) 3 5 // show (3) calles show(prev[3]=4) and prints 4
|
show(2) 4 3 5 //.......
|
show(0) 2 4 3 5 //
|
0 2 4 3 5
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
I think our solutions are implemented differently.
I understand, that it would be nice to restore the path recursively from some path-array. But I have problems on what to write to this path-array. Here is my commented code, I think you will understand what I meant there.
Hope you might help me
I understand, that it would be nice to restore the path recursively from some path-array. But I have problems on what to write to this path-array. Here is my commented code, I think you will understand what I meant there.
Code: Select all
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
#define F(i, e) for(int i = 0; i < e; i++)
#define FB(i, s) for (int i = s-1; i>=0; i--)
#define G(i, s, e) for(int i = s; i <= e; i++)
#define OUT(a) for (int ttx=0; ttx<a.size(); ttx++) cout << a[ttx] << " "; cout << endl;
int main(int argc, char* argv[]) {
int ci=0,i,j,k,l,m,n;
int a[81][81],b[81][81];
string s1,s2;
while (!cin.eof()) {
cin >> s1;
if (cin.eof())
break;
cin >> s2;
//INITIALIZING ARRAYS...
ci++;
F(i,81)
F(j,81)
a[i][j] = 0;
a[0][0] = 0; //ARRAY a IS FOR THE EDIT COST (distance) (a[i,j] - cost (s1[1..i]->s2[1..j])
//HERE IS THE DYNAMIC PROGRAMMING PART.
G(i,1,s1.length())
a[i][0] = i;
G(i,1,s2.length())
a[0][i] = i;
int val,cm;
G(i,0,s1.length()-1)
G(j,0,s2.length()-1) {
val = (s1[i]==s2[j]) ? 0 : 1;
cm = min (a[i][j]+val,min(a[i][j+1]+1,a[i+1][j]+1)); //cm - store what we choose: REPLACE, DELETE or INSERT
a[i+1][j+1] = cm;
if (j>i) //!!
b[i+1][j+1]=1; //INSERT (if length of initial string s1 is less than length of s2
else
if (cm==a[i][j]+val)
b[i+1][j+1] = (s1[i]==s2[j]) ? 0 : 3; //REPLACE if s1[i]!=s2[j] or DO NOTHING if they are equal
else if (cm==a[i][j+1]+1)
b[i+1][j+1] = 2; //DELETE
else
b[i+1][j+1] = 1; //INSERT
}
cout << a[s1.length()][s2.length()] << endl;
//UPPER STRING OUTPUTS DISTANCE (answer) correctly
//BELOW IS THE WRONG PART OF THE CODE: RESTORING THE PATH
i = s1.length();
j = s2.length();
F(k,a[s1.length()][s2.length()]) {
l = b[i][j];
if (l==1) {
cout << "Insert " << i << "," << s2[j-1] << endl;
i--;j--;
}else if (l==2) {
cout << "Delete " << i << endl;
j--;i--;
}else if (l==3) {
cout << "Replace " << i << "," << s2[j-1] << endl;
i--;j--;
}else{
i--;j--;
}
}
}
return 0;
}
Now I lay me down to sleep...
my profile
my profile
-
- New poster
- Posts: 6
- Joined: Tue Jun 08, 2010 4:01 pm
Re: 526 String Editing
Code: Select all
Code Removed - Got AC
But I'm still getting WA
I used a DP with backtracing and I don't know where'e my code is wrong.
Could someone help me please?
PS: It was a silly mistake, I forgot a +1 in the code
-
- New poster
- Posts: 31
- Joined: Thu Nov 24, 2011 12:08 am
Re: 526 String Editing
In the output specification it is said that
is this output valid for input-2:
so, are there multiple outputs?Actually many command lists can satisfy the request, but only one of them is required.
is this output valid for input-2:
Code: Select all
4
1 Insert 3,b
2 Insert 5,a
3 Insert 6,a
4 Insert 7,a