#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; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2013年8月21日
UVa 164 - String Computer
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言