gistfile1.txt

// initialize this with the maximum possible distance:
Dbest = M+N;

P = 0;
while (true) {
    // the minimum possible distance for the current P value
    Dmin = 2*(P-1) + delta;

    // if the minimum possible distance is >= our best-known distance, we can halt
    if (Dmin >= Dbest) return Dbest;

    // adaptive bound for the forward looping
    bound = min(delta, ((Dbest-delta)/2)-(2*(P-1)));

    // advance forward diagonals
    for (ku = -P, kd = P+delta;  ku <= bound;  ku += 1) {
        y = max(1+Vf[ku-1], Vf[ku+1]);
        x = y-ku;

        // path overlap detected
        if (y >= Vr[ku]) {
            vf = (ku>delta) ? (P + delta - ku) : P;
            vr = (ku<0) ? (P-1 + ku) : P-1;
            Dbest = min(Dbest, 2*(vf+vr)+delta);
            break;
        }

        // extend forward snake
        if (N >= M) {
            while (x < M  &&  y < N  &&  equal(S1[x], S2[y])) { x += 1;  y += 1; }
        } else {
            while (x < N  &&  y < M  &&  equal(S1[y], S2[x])) { x += 1;  y += 1; }
        }

        Vf[ku] = y;

        if (kd <= delta) continue;

        y = max(1+Vf[kd-1], Vf[kd+1]);
        x = y-kd;

        // path overlap detected
        if (y >= Vr[kd]) {
            vf = (kd>delta) ? (P + delta - kd) : P;
            vr = (kd<0) ? (P-1 + kd) : P-1;
            Dbest = min(Dbest, 2*(vf+vr)+delta);
            break;
        }

        // extend forward snake
        if (N >= M) {
            while (x < M  &&  y < N  &&  equal(S1[x], S2[y])) { x += 1;  y += 1; }
        } else {
            while (x < N  &&  y < M  &&  equal(S1[y], S2[x])) { x += 1;  y += 1; }
        }

        Vf[kd] = y;
        kd -= 1;
    }

    // adaptive bound for the reverse looping
    bound = max(diff_type(0), ((delta-Dbest)/2)+delta+(2*P));

    // advance reverse-path diagonals:
    for (kd=P+delta, ku=-P;  kd >= bound;  kd -= 1) {
        y = min(Vr[kd-1], Vr[kd+1]-1);
        x = y-kd;

        // path overlap detected
        if (y <= Vf[kd]) {
            vf = (kd>delta) ? (P + delta - kd) : P;
            vr = (kd<0) ? (P + kd) : P;
            Dbest = min(Dbest, 2*(vf+vr)+delta);
            break;
        }

        // extend reverse snake
        if (N >= M) {
            while (x > 0  &&  y > 0  &&  equal(S1[x-1], S2[y-1])) { x -= 1;  y -= 1; }
        } else {
            while (x > 0  &&  y > 0  &&  equal(S1[y-1], S2[x-1])) { x -= 1;  y -= 1; }
        }

        Vr[kd] = y;

        if (ku >= 0) continue;

        y = min(Vr[ku-1], Vr[ku+1]-1);
        x = y-ku;

        // path overlap detected
        if (y <= Vf[ku]) {
            vf = (ku>delta) ? (P + delta - ku) : P;
            vr = (ku<0) ? (P + ku) : P;
            Dbest = min(Dbest, 2*(vf+vr)+delta);
            break;
        }

        // extend reverse snake
        if (N >= M) {
            while (x > 0  &&  y > 0  &&  equal(S1[x-1], S2[y-1])) { x -= 1;  y -= 1; }
        } else {
            while (x > 0  &&  y > 0  &&  equal(S1[y-1], S2[x-1])) { x -= 1;  y -= 1; }
        }

        Vr[ku] = y;
        ku += 1;
    }
}