Diffアルゴリズム、つまり最短の編集グラフパス

Question

2つのコマンドライン引数の文字で動作する有名な「diff」ペーパーhereのアルゴリズムを理解しようとしています。しかし、私のコードは私が期待した結果を生み出すものではありません。私は可能な限りその変数に一致するようにアルゴリズムを書いた：ここ

は私のコードは（コードの壁については申し訳ありません）です：

a = argv[1]; 
    b = argv[2]; 
    alen = strlen(a); 
    blen = strlen(b); 
    tlen = alen + blen; 
    maxd = tlen; 

    vp = (int *)calloc(2 * maxd + 1, sizeof(int)); 

    // How I'm thinking about pointer arithmetic: 
    // vp in [0, 2*maxd + 1) == [0, 2*maxd] 
    // v in [-maxd, maxd + 1) == [-maxd, maxd] 
    v = vp + maxd; 
    v[1] = 0; 
    for (D = 0; D <= maxd; D++) { 
      for (k = -D; k <= D; k += 2) { 
        if (k == -D || (k != D && v[k-1] < v[k+1])) { 
          x = v[k + 1]; 
        } else { 
          x = v[k - 1] + 1; 
        } 
        y = x - k; 
        while (x < alen && y < blen && a[x] == b[x]) { 
          x++; 
          y++; 
        } 
        v[k] = x; 
        if (x >= alen && y >= blen) { 
          printf("SES: %d\n", D); 
          goto out; 
        } 
      } 
    } 
    printf("Nothing found. SES > %d\n", maxd); 

欠陥はここにある任意のアイデア？ 、b[y]あるべきb[x]ここ

while (x < alen && y < blen && a[x] == b[x]) { 

与える：私は、それは問題は、この行にあるようだ...それは信じられないほど難しい。この問題のためにオンラインで検索する

Answer 1

を見つけてきた

を

while (x < alen && y < blen && a[x] == b[y]) { 

この変更では、例の結果は6,0,2,1です。これは正確であるようです。