日常雜物間

#include <stdio.h>
#include <String.h>

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 'R':
    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() {
  int first = 1;
  while (gets(s1 + 1)) {
    gets(s2 + 1);
    if (!first) {
      puts("");
    }
    first = 0;
    int l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
    int dis[99][99] = {};
    memset(op, 0, sizeof(op));
    int i;
    for (i = 1; s1[i]; i++) {
      dis[i][0] = i;
      op[i][0] = 'D';
    }
    int j;
    for (j = 1; s2[j]; j++) {
      dis[0][j] = j;
      op[0][j] = 'I';
    }
    for (i = 1; s1[i]; i++) {
      for (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]) ? 'R' : 0;
        }
      }
    }
    ins = del = cnt = 0;
    printf("%d\n", dis[l1][l2]);
    show(l1, l2);
  }
  return 0;
}