LCS class

Computes the Longest Common Subsequence (LCS) distance between two strings.

The LCS algorithm finds all sub-sequences that appear in both input strings in the same order (but not necessarily contiguously). The length of the longest such sub-sequence is reported as the DistanceInfo.distance.

This implementation uses a dynamic programming approach with an O(m × n) matrix, with backtracking to enumerate all longest common sub-sequences.

final lcs = LCS();
final info = lcs.getDistanceInfo(['ABCBDAB', 'BDCABA']);
print(info.distance); // 4
print(info.lcsInfo!.lcsMatchedSubSequences); // {4: ['BCBA', 'BDAB']}

Requirements: Exactly two input strings must be provided. An ArgumentError is thrown otherwise.

Inheritance

• Object
• IDistanceCalculator
• LCS

Constructors

LCS()

Properties

hashCode → int

The hash code for this object.

no setter, inherited

height ↔ int

The length of the shorter input string. Set during computation.

getter/setter pair

runtimeType → Type

A representation of the runtime type of the object.

no setter, inherited

width ↔ int

The length of the longer input string. Set during computation.

getter/setter pair

Methods

getDistanceInfo(List<String> inputs, {CalculationOptions? options}) → DistanceInfo

Computes the distance between the given inputs.

override

getLcsInfo(String a, String b) → LcsInfo

Computes the raw LCS information for the two strings a and b.

noSuchMethod(Invocation invocation) → dynamic

Invoked when a nonexistent method or property is accessed.

inherited

toString() → String

A string representation of this object.

inherited

Operators

operator ==(Object other) → bool

The equality operator.

inherited