动画演示编辑距离

const char* s = "ecllipse"; int m = strlen(s);
const char *t = "ellipsis"; int n = strlen(t);
int d[64][64];
int pt = 50;void my_pause(int n = pt) {int paused = 0;for (int i = 0; (i < n) || paused; i++) {usleep(10000);int ch = getch();if (ch == ERR) continue;else if (ch == 'q' || ch == 'Q') exit(0);else if (ch == ' ') paused = !paused;else break;}
}void display(int ii, int jj, int flag) {for (int i = 0; i <= m; i++) {if (i == ii) attron(COLOR_PAIR(flag));mvaddch(3, 16+i*2, s[i] ? : ' '); // gcc featureif (i == ii) attroff(COLOR_PAIR(flag));}for (int j = 0; j <= n; j++) {if (j == jj) attron(COLOR_PAIR(flag));mvaddch(5, 16+j*2, t[j] ? : ' ');if (j == jj) attroff(COLOR_PAIR(flag));}for (int i = 0; i <= m; i++)for (int j = 0; j <= n; j++) {int  v = d[i][j];char s[16] = "?";if (v >= 0) sprintf(s, "%d", v, d[i][j]);if (i == ii && j == jj) attron(COLOR_PAIR(flag));mvprintw(7+i*2, 10+j*6, "%s", s);if (i == ii && j == jj) attroff(COLOR_PAIR(flag));}refresh(); my_pause();
}inline int min3 (int a, int b, int c) {int min = a;if (b < min) min = b;if (c < min) min = c;return min + 1;
}int edit_distance() {// 把s的前i个字符转换为""需要i次删除for (int i = 0; i <= m; i++) d[i][0] = i;// 把""转换为t的前j个字符需要j次插入for (int j = 0; j <= n; j++) d[0][j] = j;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s[i - 1] == '-' || s[i - 1] == t[j - 1]) {d[i][j] = d[i - 1][j - 1]; // 相同字符无需操作display(i-1, j-1, 1);}else {int a = d[i - 1][j]; // 删除display(i-1, j, 2);int b = d[i][j - 1]; // 插入display(i, j-1, 3);int c = d[i - 1][j - 1]; // 替换display(i-1, j-1, 4);d[i][j] = min3(a, b, c);}display(i, j, 5);}}return d[m][n];
}int main (int argc, char* argv[]) {if (argc == 2) pt = atoi(argv[1]);memset(d, -1, sizeof(d));initscr(); start_color();init_pair(1, COLOR_RED, COLOR_BLACK);init_pair(2, COLOR_GREEN, COLOR_BLACK);init_pair(3, COLOR_CYAN, COLOR_BLACK);init_pair(4, COLOR_MAGENTA, COLOR_BLACK);init_pair(5, COLOR_WHITE, COLOR_GREEN);cbreak(); noecho(); timeout(0); curs_set(0);atexit((void (*)())endwin);int n = edit_distance();display(m, n, 0);my_pause(1000);return n;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <ncurses.h>