526 String Editing

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

Moderator: Board moderators

Why wrong?

Postby wanderley2k » Mon May 16, 2005 5:35 am

I do this algorithm and I don
wanderley2k
New poster
 
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Postby wanderley2k » Sun Jun 05, 2005 4:07 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

wanderley2k
New poster
 
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

526 edit string trace back operations

Postby temper_3243 » Tue Aug 02, 2005 7:56 am

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: 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 for only number of changes -------------------

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
temper_3243
Experienced poster
 
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Postby sclo » Mon Feb 13, 2006 9:13 am

This question is a very standard dp that should be in every textbooks. If you get WA on this one, probably you didn't read the input correctly. You have to make sure to read the whole line, including the spaces.
sclo
Guru
 
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada

Postby andre_abrantes » Mon Jun 05, 2006 4:54 am

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!
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;
}
andre_abrantes
New poster
 
Posts: 3
Joined: Mon Jun 05, 2006 4:44 am
Location: Rio de Janeiro, Brasil

Postby karu » Wed Jun 28, 2006 12:36 pm

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
karu
New poster
 
Posts: 5
Joined: Tue Jun 13, 2006 5:31 am
Location: New Zealand

Postby andysoft » Mon Aug 06, 2007 1:22 pm

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.
Now I lay me down to sleep...
my profile
andysoft
Experienced poster
 
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS

Postby emotional blind » Mon Aug 06, 2007 4:12 pm

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


It works like this:
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


hope it helps
User avatar
emotional blind
A great helper
 
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh

Postby andysoft » Tue Aug 07, 2007 10:43 am

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


Hope you might help me
Now I lay me down to sleep...
my profile
andysoft
Experienced poster
 
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS

Re: 526 String Editing

Postby willmetalufg » Sun Aug 07, 2011 2:58 am

Code: Select all
 Code Removed - Got AC


I tried with many examples I found in the forum and it seems correct.
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
willmetalufg
New poster
 
Posts: 6
Joined: Tue Jun 08, 2010 4:01 pm

Re: 526 String Editing

Postby mostafiz93 » Tue Jul 24, 2012 3:43 pm

In the output specification it is said that
Actually many command lists can satisfy the request, but only one of them is required.


so, are there multiple outputs?

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
mostafiz93
New poster
 
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 526 String Editing

Postby brianfry713 » Tue Jul 24, 2012 10:35 pm

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.
brianfry713
Guru
 
Posts: 3490
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 526 String Editing

Postby mostafiz93 » Wed Jul 25, 2012 12:59 am

empty string will be given as input.
i got AC after handling it.
mostafiz93
New poster
 
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 526 String Editing

Postby @ce » Sat May 18, 2013 1:00 pm

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
User avatar
@ce
Learning poster
 
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 526 String Editing

Postby brianfry713 » Wed May 22, 2013 2:27 am

Try input:
Code: Select all
iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx
Your code is generating this string:
Code: Select all
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphuthdqcpkhdnuvlgslx
brianfry713
Guru
 
Posts: 3490
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Previous

Return to Volume V

Who is online

Users browsing this forum: No registered users and 1 guest