- char *topush;
- /* Construct the diff
- function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
- if i > 0 and j > 0 and X[i] = Y[j]
- printDiff(C, X, Y, i-1, j-1)
- print " " + X[i]
- else
- if j > 0 and (i = 0 or C[i,j-1] >= C[i-1,j])
- printDiff(C, X, Y, i, j-1)
- print "+ " + Y[j]
- else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
- printDiff(C, X, Y, i-1, j)
- print "- " + X[i]
- */
-
- if (i >= 0 && j >= 0 && !strcmp(xbt_dynar_get_as(da, i, char *),
- xbt_dynar_get_as(db, j, char *))) {
- diff_build_diff(res, C, da, db, i - 1, j - 1);
- topush = bprintf(" %s", xbt_dynar_get_as(da, i, char *));
- xbt_dynar_push(res, &topush);
- } else if (j >= 0 &&
- (i <= 0 || j == 0
- || xbt_matrix_get_as(C, i, j - 1,
- int) >= xbt_matrix_get_as(C, i - 1, j,
- int))) {
- diff_build_diff(res, C, da, db, i, j - 1);
- topush = bprintf("+ %s", xbt_dynar_get_as(db, j, char *));
- xbt_dynar_push(res, &topush);
- } else if (i >= 0 &&
- (j <= 0
- || xbt_matrix_get_as(C, i, j - 1, int) < xbt_matrix_get_as(C,
- i
- -
- 1,
- j,
- int)))
- {
- diff_build_diff(res, C, da, db, i - 1, j);
- topush = bprintf("- %s", xbt_dynar_get_as(da, i, char *));
- xbt_dynar_push(res, &topush);
- } else if (i <= 0 && j <= 0) {
- return;
+ const int delta = len_a - len_b;
+ const int limit = (len_a + len_b) / 2;
+ int kmin;
+ int kmax;
+ int k;
+ int p = -1;
+
+ if (delta >= 0) {
+ kmin = 0;
+ kmax = delta;
+ } else {
+ kmin = delta;
+ kmax = 0;
+ }
+ for (k = kmin; k <= kmax; k++)
+ fp[k] = -1;
+ do {
+ p++;
+ fp[kmin - p - 1] = fp[kmax + p + 1] = -1;
+ for (k = kmax + p; k > delta; k--)
+ diff_snake(vec_a, a0, len_a, vec_b, b0, len_b, seqs, fp, k, limit);
+ for (k = kmin - p; k <= delta; k++)
+ diff_snake(vec_a, a0, len_a, vec_b, b0, len_b, seqs, fp, k, limit);
+ } while (fp[delta] != len_a);
+
+ subseq->x = a0 + seqs[delta].x;
+ subseq->y = b0 + seqs[delta].y;
+ subseq->len = seqs[delta].len;
+ return abs(delta) + 2 * p;;
+}
+
+/* Finds a longest common subsequence.
+ * Returns its length.
+ */
+static int diff_compute_lcs(const char *vec_a[], int a0, int len_a,
+ const char *vec_b[], int b0, int len_b,
+ xbt_dynar_t common_sequence,
+ struct subsequence *seqs, int *fp)
+{
+ if (len_a > 0 && len_b > 0) {
+ struct subsequence subseq;
+ int ses_len = diff_middle_subsequence(vec_a, a0, len_a, vec_b, b0, len_b,
+ &subseq, seqs, fp);
+ int lcs_len = (len_a + len_b - ses_len) / 2;
+ if (lcs_len == 0) {
+ return 0;
+ } else if (ses_len > 1) {
+ int lcs_len1 = subseq.len;
+ if (lcs_len1 < lcs_len)
+ lcs_len1 += diff_compute_lcs(vec_a, a0, subseq.x - a0,
+ vec_b, b0, subseq.y - b0,
+ common_sequence, seqs, fp);
+ if (subseq.len > 0)
+ xbt_dynar_push(common_sequence, &subseq);
+ if (lcs_len1 < lcs_len) {
+ int u = subseq.x + subseq.len;
+ int v = subseq.y + subseq.len;
+ diff_compute_lcs(vec_a, u, a0 + len_a - u, vec_b, v, b0 + len_b - v,
+ common_sequence, seqs, fp);
+ }
+ } else {
+ int len = MIN(len_a, len_b) - subseq.len;
+ if (subseq.x == a0 && subseq.y == b0) {
+ if (subseq.len > 0)
+ xbt_dynar_push(common_sequence, &subseq);
+ if (len > 0) {
+ struct subsequence subseq0 = {a0 + len_a - len,
+ b0 + len_b - len, len};
+ xbt_dynar_push(common_sequence, &subseq0);
+ }
+ } else {
+ if (len > 0) {
+ struct subsequence subseq0 = {a0, b0, len};
+ xbt_dynar_push(common_sequence, &subseq0);
+ }
+ if (subseq.len > 0)
+ xbt_dynar_push(common_sequence, &subseq);
+ }
+ }
+ return lcs_len;