- xbt_matrix_t C = xbt_matrix_new(len_a, len_b, sizeof(int), NULL);
- int i, j;
-
- /* Compute the LCS */
- /*
- function LCSLength(X[1..m], Y[1..n])
- C = array(0..m, 0..n)
- for i := 0..m
- C[i,0] = 0
- for j := 1..n
- C[0,j] = 0
- for i := 1..m
- for j := 1..n
- if X[i] = Y[j]
- C[i,j] := C[i-1,j-1] + 1
- else:
- C[i,j] := max(C[i,j-1], C[i-1,j])
- return C[m,n]
- */
- for (i = 0; i < len_a; i++)
- for (j = 0; j < len_b; j++) {
-
- if (!strcmp(xbt_dynar_get_as(da, i, char *),
- xbt_dynar_get_as(db, j, char *)))
- *((int *) xbt_matrix_get_ptr(C, i, j)) = diff_get(C, i - 1, j - 1) + 1;
- else
- *((int *) xbt_matrix_get_ptr(C, i, j)) = max(diff_get(C, i, j - 1),
- diff_get(C, i - 1, j));
+ 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);
+ }