Why wrong?
Posted: Mon May 16, 2005 5:35 am
I do this algorithm and I don
The Online Judge board
https://onlinejudge.org/board/
Code: Select all
while(cin>>str1>>str2) // wrong
while(!cin.eof()) {
cin>>str1;
if (cin.eof()) break;
cin>>str2;
} // It is correct
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
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
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
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
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;
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;
}
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
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
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;
}
Code: Select all
Code Removed - Got AC
so, are there multiple outputs?Actually many command lists can satisfy the request, but only one of them is required.
Code: Select all
4
1 Insert 3,b
2 Insert 5,a
3 Insert 6,a
4 Insert 7,a