MetricLCS.md

Metric Longest Common Subsequence

Distance metric based on Longest Common Subsequence, from the notes "An LCS-based string metric" by Daniel Bakkelund.

The distance is computed as 1 - |LCS(s1, s2)| / max(|s1|, |s2|)

Example

val lcs = MetricLCS()
println(lcs.distance("ABCDEFG", "ABCDEFHJKL"))
println(lcs.distance("ABDEF", "ABDIF"))

Output:

0.4
0.19999999999999996

Links

• An LCS-based string metric