diffSequences<T> function

List<SeqDiffOp<T>> diffSequences<T>(List<T> a, List<T> b)

Computes the LCS-based edit script that turns a into b: a list of equal / delete / insert ops in input order. delete items appear only in a, insert items only in b, and the equal items are their longest common subsequence. O(n·m) time and space. Audited: 2026-06-12 11:26 EDT

Implementation

List<SeqDiffOp<T>> diffSequences<T>(List<T> a, List<T> b) {
  final int n = a.length;
  final int m = b.length;
  // dp[i][j] = LCS length of a[i..] and b[j..]; computed back-to-front so the
  // forward backtrack below can greedily reconstruct the script.
  final List<List<int>> dp = List<List<int>>.generate(
    n + 1,
    (_) => List<int>.filled(m + 1, 0),
  );
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      if (a[i] == b[j]) {
        dp[i][j] = dp[i + 1][j + 1] + 1;
      } else {
        final int down = dp[i + 1][j];
        final int right = dp[i][j + 1];
        dp[i][j] = down >= right ? down : right;
      }
    }
  }
  return _backtrack(a, b, dp);
}