longestCommonSubsequenceLength<E> function

int longestCommonSubsequenceLength<E>(
  1. List<E> source,
  2. List<E> target, {
  3. DualEqualityTest<E, E>? test,
})

Returns the length of the longest common subsequence of two list of items.

Parameters

  • source and target are two list of items.
  • test is an optional equality matcher.

Details

Common subsequence between two list of items is a set of items appearing in both in the same order. Unlike substrings, the subsequences are not required occupy consecutive positions.

This functions returns the length of the longest common subsequence between source and target without modifying their contents.

This is similar to Levenshtein distance, where only insertion and deletion operations are permitted, and substitution is not.

If n is the length of source and m is the length of target,
Complexity: Time O(nm) | Space O(n)

Implementation

int longestCommonSubsequenceLength<E>(
  List<E> source,
  List<E> target, {
  DualEqualityTest<E, E>? test,
}) {
  if (source.length > target.length) {
    // since this is symmetric, we can swap them to optimize the inner loop
    List<E> t = target;
    target = source;
    source = t;
  }
  if (test == null) {
    return longestCommonSubsequenceLengthDefault(source, target);
  }
  return longestCommonSubsequenceLengthCustom(source, target, test);
}