最长公共子串

问题：

找出最长、连续的子字符串

思路：

遍历X、Y的所有子字符串，找出最长公共后缀，则最长公共后缀的长度就是最长公共子串的长度。

LCSSuffix[i][j] = LCSSuffix[i - 1][j - 1] + 1 （若X[i - 1] == Y[j - 1]）
                          0                                     （若X[i - 1] != Y[j - 1]）

代码

class LCS
{
    // Function to find Longest common substring of sequences
    // X[0..m-1] and Y[0..n-1]
    public static String LCS(String X, String Y, int m, int n)
    {
        int maxlen = 0;         // stores the max length of LCS
        int endingIndex = m;    // stores the ending index of LCS in X

        // lookup[i][j] stores the length of LCS of substring
        // X[0..i-1], Y[0..j-1]
        int[][] lookup = new int[m + 1][n + 1];

        // fill the lookup table in bottom-up manner
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                // if current character of X and Y matches
                if (X.charAt(i - 1) == Y.charAt(j - 1))
                {
                    lookup[i][j] = lookup[i - 1][j - 1] + 1;

                    // update the maximum length and ending index
                    if (lookup[i][j] > maxlen)
                    {
                        maxlen = lookup[i][j];
                        endingIndex = i;
                    }
                }
            }
        }

        // return Longest common substring having length maxlen
        return X.substring(endingIndex - maxlen, endingIndex);
    }

    // main function
    public static void main(String[] args)
    {
        String X = "ABC", Y = "BABA";
        int m = X.length(), n = Y.length();

        // Find Longest common substring
        System.out.print("The Longest common substring is "
                        + LCS(X, Y, m, n));
    }
}

最长递增子序列

public static int LIS(int[] A, int i, int n, int prev) {
        if (i == n) {
            return 0;
        }

        int excludeCurrentIndex = LIS(A, i + 1, n, prev);

        int includeCurrentIndex = 0;
        if (A[i] > prev) {
            includeCurrentIndex = 1 + LIS(A, i + 1, n, A[i]);
        }

        return Integer.max(excludeCurrentIndex, includeCurrentIndex);
    }


    public static int LIS(int[] A) {
        //存储以A[i]结尾的递增子序列的最大长度.
        int[] L = new int[A.length];

        L[0] = 1;

        for (int i = 1; i < A.length; i++) {
            //从A[0..i-1]中挑出比A[i]小的元素.
            for (int j = 0; j < i; j++) {
                if (A[j] < A[i] && L[j] > L[i]) {
                    L[i] = L[j];
                }
            }

            L[i]++;
        }

        return Arrays.stream(L).max().getAsInt();
    }

打印最长递增子序列的版本

public static int[] findLCS(int[] A) {
        //存储以A[i]结尾的递增子序列的最大长度.
        int[] L = new int[A.length];

        L[0] = 1;

        for (int i = 1; i < A.length; i++) {
            //从A[0..i-1]中挑出比A[i]小的元素.
            for (int j = 0; j < i; j++) {
                if (A[j] < A[i] && L[j] > L[i]) {
                    L[i] = L[j];
                }
            }

            L[i]++;
        }

        int maxLen = 0;
        int index = 0;

        for (int i = 0; i < L.length; i++) {
            if (L[i] > maxLen) {
                maxLen = L[i];
                index = i;
            }
        }

        int[] result = new int[maxLen];

        for (int i = index; i >= 0; i--) {
            if (L[i] == maxLen) {
                maxLen--;
                result[maxLen] = A[i];
            }
        }
        return result;
    }

O(nlogn)算法复杂度的版本

定义数组outputList[A.length]，outputList[i]表示所有长度为i+1的递增子序列的最小尾元素。
容易证明：outputList[]是一个递增数组。

public int findLIS2(int[] A) {
        ArrayList<Integer> outputList = new ArrayList<>();

        for (int x : A) {           
            int insertPos = lowerBound(outputList, 0, outputList.size(), x);
            if (insertPos >= lis.size()) {
                lis.add(x);
            } else {
                lis.set(insertPos, x);
            }
        }

        return lis.size();
    }

private int lowerBound(ArrayList<Integer> list, int first, int last, int target) {
    while (first != last) {

        int mid = first + (last - first) / 2;

        if (target > list.get(mid)) {
            first = mid + 1;
        } else {
            last = mid;
        }
    }

    return first;
}