2013年8月21日

UVa 526 - String Distance and Transform Process

#include <cstdio>
#include <cstring>
 
inline int min(int a, int b) {
  return a < b ? a : b;
}
 
char s1[99], s2[99];
int op[99][99], ins, del, cnt;
 
void show(int i, int j) {
  switch (op[i][j]) {
    case 0:
      show(i - 1, j - 1);
      break;
    case 'C':
      show(i - 1, j - 1);
      printf("%d Replace %d,%c\n", ++cnt, i + ins - del, s2[j]);
      break;
    case 'D':
      show(i - 1, j);
      printf("%d Delete %d\n", ++cnt, i + ins - del);
      del++;
      break;
    case 'I':
      show(i, j - 1);
      printf("%d Insert %d,%c\n", ++cnt, j, s2[j]);
      ins++;
      break;
  }
}
 
int main() {
  bool first = true;
  while (gets(s1 + 1)) {
    gets(s2 + 1);
    if (!first) {
      puts("");
    }
    first = false;
    int l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
    int dis[99][99] = {};
    memset(op, 0, sizeof(op));
    for (int i = 1; s1[i]; i++) {
      dis[i][0] = i;
      op[i][0] = 'D';
    }
    for (int j = 1; s2[j]; j++) {
      dis[0][j] = j;
      op[0][j] = 'I';
    }
    for (int i = 1; s1[i]; i++) {
      for (int j = 1; s2[j]; j++) {
        int m = min(dis[i - 1][j - 1] + (s1[i] != s2[j]), min(dis[i - 1][j] + 1, dis[i][j - 1] + 1));
        dis[i][j] = m;
        if (m == dis[i - 1][j] + 1) {
          op[i][j] = 'D';
        } else if (m == dis[i][j - 1] + 1) {
          op[i][j] = 'I';
        } else {
          op[i][j] = (s1[i] != s2[j]) ? 'C' : 0;
        }
      }
    }
    ins = del = cnt = 0;
    printf("%d\n", dis[l1][l2]);
    show(l1, l2);
  }
  return 0;
}

沒有留言:

張貼留言