2013年8月21日

UVa 164 - String Computer

#include <cstdio>
#include <cstring>
 
inline int min(int a, int b) {
  return a < b ? a : b;
}
 
char s1[99], s2[99];
int op[29][29], ins, del;
 
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("C%c%02d", s2[j], i + ins - del);
      break;
    case 'D':
      show(i - 1, j);
      printf("D%c%02d", s1[i], i + ins - del);
      del++;
      break;
    case 'I':
      show(i, j - 1);
      printf("I%c%02d", s2[j], j);
      ins++;
      break;
  }
}
 
int main() {
  while (scanf("%s", s1 + 1) && s1[1] != '#') {
    scanf("%s", s2 + 1);
    int l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
    int dis[29][29] = {};
    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 = 0;
    show(l1, l2);
    puts("E");
  }
  return 0;
}

沒有留言:

張貼留言