Text 0.4.0 lcs subsequencelength

Lodestar.Text 0.4.0. This page is frozen at that release. Read the current documentation for what main says now. A link to a decision or a migration page follows main, and leaves the archive.

Lcs.SubsequenceLength

Returns the length of the longest sequence of characters that appears in both inputs in the same order, with gaps allowed.

public static int SubsequenceLength(ReadOnlySpan<char> a, ReadOnlySpan<char> b, TextElement element = TextElement.Utf16Unit)
public static int SubsequenceLength<T>(ReadOnlySpan<T> a, ReadOnlySpan<T> b) where T : IEquatable<T>

Parameters — a and b are the two strings to compare. element says what counts as one character: TextElement.Utf16Unit by default, or TextElement.CodePoint to count an emoji once. The second overload compares any two spans of an IEquatable<T>, which is how you get the longest common run of words rather than of characters.

Returns — int, at most the length of the shorter input, and 0 when either is empty.

Example — ittn survives in both, out of six and seven characters.

using Lodestar.Text.Distances;

int n = Lcs.SubsequenceLength("kitten", "sitting");   // => 4

Remarks — this is the classic LCS, and it is the thing to call when you want the shared material itself rather than a score derived from it: how much of a document survived an edit, how much of a template a candidate string fills in. Indel.Distance is precisely len(a) + len(b) - 2 × SubsequenceLength(a, b), so if you need both, call this and do the arithmetic rather than paying for two passes.

The trap is that it is a raw length with no upper bound of its own, and the number alone says nothing: a shared run of 4 is most of a six-letter word and nothing at all in a paragraph. It is also not what SubstringLength returns — this one allows gaps, and the two answers differ on almost every real pair.

Applies to — net10.0, netstandard2.0.

See also — Lcs.SubstringLength, Indel.Distance, RatcliffObershelp.Similarity, the Python equivalence table.