+/* 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;
+ } else {
+ return 0;
+ }
+}
+
+static int diff_member(const char *s, const char *vec[], int from, int to)
+{
+ for ( ; from < to ; from++)
+ if (!strcmp(s, vec[from]))
+ return 1;
+ return 0;
+}
+
+/* Extract common prefix.
+ */
+static void diff_easy_prefix(const char *vec_a[], int *a0_p, int *len_a_p,
+ const char *vec_b[], int *b0_p, int *len_b_p,
+ xbt_dynar_t common_sequence)
+{
+ int a0 = *a0_p;
+ int b0 = *b0_p;
+ int len_a = *len_a_p;
+ int len_b = *len_b_p;
+
+ while (len_a > 0 && len_b > 0) {
+ struct subsequence subseq = {a0, b0, 0};
+ while (len_a > 0 && len_b > 0 && !strcmp(vec_a[a0], vec_b[b0])) {
+ a0++, len_a--;
+ b0++, len_b--;
+ subseq.len++;
+ }
+ if (subseq.len > 0)
+ xbt_dynar_push(common_sequence, &subseq);
+ if (len_a > 0 && len_b > 0 &&
+ !diff_member(vec_a[a0], vec_b, b0 + 1, b0 + len_b)) {
+ a0++, len_a--;
+ } else {
+ break;
+ }
+ }
+
+ *a0_p = a0;
+ *b0_p = b0;
+ *len_a_p = len_a;
+ *len_b_p = len_b;
+}
+
+/* Extract common suffix.
+ */
+static void diff_easy_suffix(const char *vec_a[], int *a0_p, int *len_a_p,
+ const char *vec_b[], int *b0_p, int *len_b_p,
+ xbt_dynar_t common_suffix)
+{
+ int a0 = *a0_p;
+ int b0 = *b0_p;
+ int len_a = *len_a_p;
+ int len_b = *len_b_p;
+
+ while (len_a > 0 && len_b > 0){
+ struct subsequence subseq;
+ subseq.len = 0;
+ while (len_a > 0 && len_b > 0 &&
+ !strcmp(vec_a[a0 + len_a - 1], vec_b[b0 + len_b - 1])) {
+ len_a--;
+ len_b--;
+ subseq.len++;
+ }
+ if (subseq.len > 0) {
+ subseq.x = a0 + len_a;
+ subseq.y = b0 + len_b;
+ xbt_dynar_push(common_suffix, &subseq);
+ }
+ if (len_a > 0 && len_b > 0 &&
+ !diff_member(vec_b[b0 + len_b - 1], vec_a, a0, a0 + len_a - 1)) {
+ len_b--;
+ } else {
+ break;
+ }
+ }
+
+ *a0_p = a0;
+ *b0_p = b0;
+ *len_a_p = len_a;
+ *len_b_p = len_b;