で、書いてみた。

#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に落とすかなんだろうなあ。
つーか、これバグがありそうだ。近いうちに直します。