Class LongestCommonSubsequence

  • All Implemented Interfaces:
    StringDistance, java.io.Serializable

    @Immutable
    public class LongestCommonSubsequence
    extends java.lang.Object
    implements StringDistance
    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. It is used by the diff utility, by Git for reconciling multiple changes, etc. The LCS distance between Strings X (length n) and Y (length m) is n + m - 2 |LCS(X, Y)| min = 0 max = n + m 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. ! This class currently implements the dynamic programming approach, which has a space requirement O(m * n)!
    See Also:
    Serialized Form
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      double distance​(java.lang.String s1, java.lang.String s2)
      Return the LCS distance between strings s1 and s2, computed as |s1| + |s2| - 2 * |LCS(s1, s2)|.
      int length​(java.lang.String s1, java.lang.String s2)
      Return the length of Longest Common Subsequence (LCS) between strings s1 and s2.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • LongestCommonSubsequence

        public LongestCommonSubsequence()
    • Method Detail

      • distance

        public final double distance​(java.lang.String s1,
                                     java.lang.String s2)
        Return the LCS distance between strings s1 and s2, computed as |s1| + |s2| - 2 * |LCS(s1, s2)|.
        Specified by:
        distance in interface StringDistance
        Parameters:
        s1 - The first string to compare.
        s2 - The second string to compare.
        Returns:
        the LCS distance between strings s1 and s2, computed as |s1| + |s2| - 2 * |LCS(s1, s2)|
        Throws:
        java.lang.NullPointerException - if s1 or s2 is null.
      • length

        public final int length​(java.lang.String s1,
                                java.lang.String s2)
        Return the length of Longest Common Subsequence (LCS) between strings s1 and s2.
        Parameters:
        s1 - The first string to compare.
        s2 - The second string to compare.
        Returns:
        the length of LCS(s1, s2)
        Throws:
        java.lang.NullPointerException - if s1 or s2 is null.