c - 差异算法，即最短编辑图路径

Question

我试图从著名的“diff”论文中理解算法 here , 在两个命令行参数中的字符上运行。但是，我的代码没有产生我期望的结果。我已经编写了尽可能匹配它们的变量的算法:

$ ./diff abbcabba cbabac #Hmm.. I think it should be 5
SES: 10  
$ ./diff abcdefg abcdefg #0! Great!
SES: 0
$ ./diff abcXefg abcYefg # 2 seems reasonable
SES: 2
$ ./diff abcXefg abcefg # clearly wrong
SES: 7

这是我的代码(抱歉代码墙):

    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);

知道这里的缺陷在哪里吗？我发现很难在网上搜索这个问题...

Answer 1

看来问题出在这一行:

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

这里的b[x]应该是b[y]，它给出:

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

通过此更改，您的示例的结果为 6、0、2 和 1。这似乎是准确的。