Разностный алгоритм, т.е. кратчайший путь редактирования графа - PullRequest
Новая
       16

Разностный алгоритм, т.е. кратчайший путь редактирования графа

4 голосов
/ 02 марта 2012

Я пытаюсь понять алгоритм из знаменитой статьи 'diff' здесь , работающей на символах в двух аргументах командной строки. Однако мой код не дает ожидаемых результатов. Я написал алгоритм для максимально возможного соответствия их переменных: 

$ ./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);

Есть идеи, где здесь недостаток? Мне было невероятно трудно найти эту проблему в Интернете ...

1 Ответ

4 голосов
/ 02 марта 2012

Кажется, что проблема в этой строке: 

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. Кажется, что это точно.

...