Voltar

## Distancia de edição - Paradigmas

0 Curtidas
```/* Dynamic Programming: Edit Distance (with path recovery)
=================================================================
Description: Computes the edit distance for two strings.  Namely
this involves certain costs for Replacement,
Insertions and Deletions.  Given these costs, and
two words, this program calculates the minimum cost
way to transform the first string to the second.  An
added bonus is the PathRecovery() subroutine, which
prints out exactly what happens step by step.

Complexity:  O(N^2) where N is the size of the larger of the two
strings
-----------------------------------------------------------------
Author:      Gilbert Lee
Date:        May 10, 2002
References:
-----------------------------------------------------------------
Reliability: 1 (Spain Problem 526)

Notes:       Some modifications need to be made in order to fix
path recovery.
*/

#include
#include

#define MAXN 90

char move[MAXN][MAXN];  /* Type of command used */
int  g[MAXN][MAXN];      /* Cost of changes */

int editDistance(char *src, char *dst, int replace, int insert, int delete){
int i, j, l1, l2;

l1 = strlen(src);
l2 = strlen(dst);

for(j = 0; j <= l1; j++){
g[0][j] = j;
move[0][j] = 'D';
}

for(i = 1; i <= l2; i++){
g[i][0] = i;
move[i][0] = 'I';

for(j = 1; j <= l1; j++){
g[i][j] = g[i-1][j-1]+replace;
move[i][j] = 'R';

if(g[i-1][j]+insert < g[i][j]){
g[i][j] = g[i-1][j]+insert;
move[i][j] = 'I';
}

if(g[i][j-1]+delete < g[i][j]){
g[i][j] = g[i][j-1]+delete;
move[i][j] = 'D';
}

if(src[j-1] == dst[i-1] && g[i-1][j-1] < g[i][j]){
g[i][j] = g[i-1][j-1];
move[i][j] = 'N';
}
}
}
return g[l2][l1];
}

int counter;
void PathRecovery(int x, int y, int *delta, char *src, char *dst){
int ndelta;

if(x == 0 && y == 0){
*delta = 0;
return;
}
else {
switch(move[x][y]){
case 'R':
PathRecovery(x-1,y-1,&ndelta,src,dst);
*delta = ndelta;
printf("%d Replace %d,%c\n", counter++, y+ndelta, dst[x-1]);
break;
case 'I':
PathRecovery(x-1,y,&ndelta,src,dst);
*delta = ndelta+1;
printf("%d Insert %d,%c\n", counter++, y+ndelta+1, dst[x-1]);
break;
case 'D':
PathRecovery(x,y-1,&ndelta,src,dst);
*delta = ndelta-1;
printf("%d Delete %d\n", counter++, y+ndelta);
break;
case 'N':
PathRecovery(x-1,y-1,&ndelta,src,dst);
*delta = ndelta;
break;
}
}
}

int main(){
int x, first = 1, delta;
char s1[MAXN], s2[MAXN];

while(fgets(s1, MAXN, stdin)){
if(first) first = 0;
else printf("\n");
fgets(s2, MAXN, stdin);
s1[strlen(s1)-1] = 0;
s2[strlen(s2)-1] = 0;
if(first) first = 0;
else printf("\n");
x = editDistance(s1, s2, 1,1,1);
printf("%d\n", x);
counter = 1;
PathRecovery(strlen(s2), strlen(s1), &delta, s1, s2);
}
return 0;
}
```