で、書いてみた。
#include#include int main(int argc, char **argv){ char *str1, *str2; int m, n, i, j, k; int *map; scanf("%d %d", &m, &n); str1 = malloc(m + 1); str2 = malloc(n + 1); scanf("%s", str1); scanf("%s", str2); map = malloc(sizeof(int) * n * m); map[0] = (str1[0] == str2[0]) ? 0 : 1; for(j = 1; j < n; j++){ if(str1[0] == str2[j]){ map[j] = j; }else{ map[j] = map[j-1] + 1; } } for(i = 1; i < m; i++){ //update map[i * n + j] if(str1[i] == str2[0]) map[i * n] = i; else map[i * n] = map[(j-1) * n - 1] + 1; for(j = 1; j <= n; j++){ if(str1[i] == str2[j]){ map[i * n + j] = map[(i-1) * n + (j-1)]; }else{ int center = map[(i - 1) * n + (j - 1)] + 1; int left = map[(i - 1) * n + j] + 1; int right = map[i * n + j - 1] + 1; int min = center; min = min < left ? min : left; min = min < right ? min : right; map[i * n + j] = min; } } } printf("%d\n", map[n * m - 1]); return 0; }
まあ、適当に書くならこんなもんか。特に複雑なデータ構造いらないし、これを並列化するんであれば、やはりループの中身をどうやってSIMDに落とすかなんだろうなあ。
つーか、これバグがありそうだ。近いうちに直します。