Class LCS


  • public class LCS
    extends Object
    • Method Detail

      • getSerializableChangeSet

        public static <T extends SerializableList<LCS.Change<T>> getSerializableChangeSet​(T[] a,
                                                                                            T[] b)
        Constructs the minimal changeset to turn the first array into the second one. The returned changeset is guaranteed to be serializable.
        Type Parameters:
        T - the type of the array elements
        Parameters:
        a - the first array
        b - the second array
        Returns:
        the minimal changeset
      • getChangeSet

        public static <T> List<LCS.Change<T>> getChangeSet​(T[] a,
                                                           T[] b)
        Constructs the minimal changeset to turn the first array into the second one. The returned changeset is only serializable when T is serializable.
        Type Parameters:
        T - the type of the array elements
        Parameters:
        a - the first array
        b - the second array
        Returns:
        the minimal changeset
      • getLongestCommonSubsequence

        public static <T> List<T> getLongestCommonSubsequence​(T[] a,
                                                              T[] b)
        Find the longest common subsequence between arrays a and b. The algorithm that's implemented creates an index of the items in the smallest array and iterates over the largest one. During this iteration, for each sub-array consisting of the elements 0..j of the small array (j < |smallest|), the sequence with most common elements is maintained.

        The execution time and memory usage are linear for typical inputs, but will be quadratic in the worst case.