string-similarity/com.aallam.similarity/LongestCommonSubsequence

LongestCommonSubsequence

The longest common subsequence (LCS) problem consists in finding the longest subsequence common to two (or more) sequences. It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

LCS distance is equivalent to Levenshtein distance, when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion.

Constructors

constructor()

Functions

distance

fun distance(first: String, second: String): Int

Return the LCS distance between strings first (length n) and second (length m), computed as |n| + |m| - 2 * |LCS(first, second)|, with min = 0 max = n + m

length

fun length(first: String, second: String): Int

Return the length of the longest common subsequence (LCS) between strings first and second.