摘要：若且，則是和的最長公共子序列若且，則是和的最長公共子序列。遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算和的最長公共子序列時，可能要計算出和及和的最長公共子序列。

雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復制黨

本章講解：
1. LCS（最長公共子序列）O(n^2)的時間復雜度,O(n^2)的空間復雜度；
2. 與之類似但不同的最長公共子串方法。
最長公共子串用動態(tài)規(guī)劃可實現(xiàn)O(n^2)的時間復雜度，O(n^2)的空間復雜度；還可以進一步優(yōu)化，用后綴數(shù)組的方法優(yōu)化成線性時間O(nlogn)；空間也可以用其他方法優(yōu)化成線性。
3.LIS（最長遞增序列）DP方法可實現(xiàn)O(n^2)的時間復雜度，進一步優(yōu)化最佳可達到O(nlogn)

一些定義：
字符串 X， Y 長度 分別m，n

子串：字符串S的子串r[i,...,j],i<=j,表示r串從i到j這一段，也就是順次排列r[i],r[i+1],...,r[j]形成的字符串

前綴：Xi =﹤x1，?，xi﹥ 即 X 序列的前 i 個字符 (1≤i≤m)；
Yj=﹤y1，?，yj﹥即 Y 序列的前 j 個字符 (1≤j≤n)；
假定 Z=﹤z1，?，zk﹥∈LCS(X , Y)

有關后綴數(shù)組的定義

定義：
一個數(shù)列 S，如果分別是兩個或多個已知數(shù)列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
例如：輸入兩個字符串 BDCABA 和 ABCBDAB，字符串 BCBA 和 BDAB 都是是它們的最長公共子序列，則輸出它們的長度 4，并打印任意一個子序列. （Note: 不要求連續(xù)）

判斷字符串相似度的方法之一 - LCS 最長公共子序列越長，越相似。

對于一般性的 LCS 問題（即任意數(shù)量的序列）是屬于 NP-hard。但當序列的數(shù)量確定時，問題可以使用動態(tài)規(guī)劃（Dynamic Programming）在多項式時間解決。可達時間復雜度：O(m*n)
July 10分鐘講LCS視頻，

最優(yōu)子結構性質：
設序列 X= 和 Y= 的一個最長公共子序列 Z=，則：

若 xm = yn，則 zk = xm = yn 則 Zk-1 是 Xm-1 和 Yn-1 的最長公共子序列；

若 xm ≠ yn， 要么Z是 Xm-1 和 Y 的最長公共子序列，要么 Z 是X和 Yn-1 的最長公共子序列。
2.1 若 xm ≠ yn 且 zk≠xm ，則 Z是 Xm-1 和 Y 的最長公共子序列；
2.2 若 xm ≠ yn 且 zk ≠yn ，則 Z 是X和 Yn-1 的最長公共子序列。
綜合一下2 就是求二者的大者

遞歸結構：

遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算 X 和 Y 的最長公共子序列時，可能要計算出 X 和 Yn-1 及 Xm-1 和 Y 的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算 Xm-1 和 Yn-1 的最長公共子序列。

遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算 X 和 Y 的最長公共子序列時，可能要計算出 X 和 Yn-1 及 Xm-1 和 Y 的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1 和 Yn-1 的最長公共子序列。

計算最優(yōu)值：
子問題空間中，總共只有O(m*n) 個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。

長度表C 和 方向變量B：

java實現(xiàn)：

 /* 動態(tài)規(guī)劃
 * 求最長公共子序列
 * @ author by gsm
 * @ 2015.4.1
 */
import java.util.Random;
public class LCS {

    public static int[][] lengthofLCS(char[] X, char[] Y){
        /* 構造二維數(shù)組c[][]記錄X[i]和Y[j]的LCS長度 (i,j)是前綴
         * c[i][j]=0; 當 i = j = 0;
         * c[i][j]=c[i-1][j-1]+1; 當 i = j > 0; Xi == Y[i]
         * c[i][j]=max(c[i-1][j],c[i][j+1]); 當 i = j > 0; Xi != Y[i]
         * 需要計算 m*n 個子問題的長度 即 任意c[i][j]的長度
         * -- 填表過程
         */
        int[][]c = new int[X.length+1][Y.length+1];

        // 動態(tài)規(guī)劃計算所有子問題
        for(int i=1;i<=X.length;i++){
            for (int j=1;j<=Y.length;j++){
                if(X[i-1]==Y[j-1]){
                    c[i][j] = c[i-1][j-1]+1;
                }
                else if(c[i-1][j] >= c[i][j-1]){
                    c[i][j] = c[i-1][j];
                }
                else{
                    c[i][j] = c[i][j-1];
                }
            }
        }

        // 打印C數(shù)組
        for(int i=0;i<=X.length;i++){
            for (int j=0;j<=Y.length;j++){
                System.out.print(c[i][j]+" ");
            }
            System.out.println();
        }
        return c;
    }
    // 輸出LCS序列
    public static void print(int[][] arr, char[] X, char[] Y, int i, int j) {
        if(i == 0 || j == 0)
            return;
        if(X[i-1] == Y[j-1]) {
            System.out.print("element " + X[i-1] + " ");
            // 尋找的
            print(arr, X, Y, i-1, j-1);
        }else if(arr[i-1][j] >= arr[i][j-1]) {
            print(arr, X, Y, i-1, j);
        }else{
            print(arr, X, Y, i, j-1);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        char[] x ={"A","B","C","B","D","A","B"}; 
        char[] y ={"B","D","C","A","B","A"}; 
        int[][] c = lengthofLCS(x,y);
        print(c, x, y, x.length, y.length);
    }
}

定義 2 個字符串 query 和 text, 如果 query 里最大連續(xù)字符子串在 text 中存在，則返回子串長度. 例如: query="acbac"，text="acaccbabb"， 則最大連續(xù)子串為 "cba", 則返回長度 3.

這個 LCS 跟前面說的最長公共子序列的 LCS 不一樣，不過也算是 LCS 的一個變體，在 LCS 中，子序列是不必要求連續(xù)的，而子串則是 “連續(xù)” 的

我們還是像之前一樣 “從后向前” 考慮是否能分解這個問題，類似最長公共子序列的分析，這里，我們使用c[i,j] 表示 以 Xi 和 Yj 結尾的最長公共子串的長度，因為要求子串連續(xù)，所以對于 Xi 與 Yj 來講，它們要么與之前的公共子串構成新的公共子串；要么就是不構成公共子串。故狀態(tài)轉移方程

X[i-1] == Y[j-1]，c[i,j] = c[i-1,j-1] + 1；

X[i-1] != Y[j-1]，c[i,j] = 0；

對于初始化，i==0 或者 j==0，c[i,j] = 0
代碼：

public class LCString {
    public  static int lengthofLCString(String X, String Y){
        /* 構造二維數(shù)組c[][]記錄X[i]和Y[j]的LCS長度 (i,j)是前綴
         * c[i][j]=0; 當 i = j = 0;
         * c[i][j]=c[i-1][j-1]+1; 當 i = j > 0; Xi == Y[i]
         * c[i][j]=0; 當 i = j > 0; Xi != Y[i]
         * 需要計算 m*n 個子問題的長度 即 任意c[i][j]的長度
         * -- 填表過程
         */
        int[][]c = new int[X.length()+1][Y.length()+1];
        int maxlen = 0;
        int maxindex = 0;
        for(int i =1;i<=X.length();i++){
            for(int j=1;j<=Y.length();j++){
                if(X.charAt(i-1) == Y.charAt(j-1)){
                    c[i][j] = c[i-1][j-1]+1;
                    if(c[i][j] > maxlen)
                    {
                        maxlen = c[i][j];
                        maxindex = i + 1 - maxlen;
                    }
                }
            }
        }
        return maxlen;
    }

    public static void main(String[] args) {
        String X = "acbac";
        String Y = "acaccbabb";
        System.out.println(lengthofLCString(X,Y)); 
    }
}

有關后綴數(shù)組以及求最長重復子串
前面提過后綴數(shù)組的基本定義，與子串有關，可以嘗試這方面思路。由于后綴數(shù)組最典型的是尋找一個字符串的重復子串，所以，對于兩個字符串，我們可以將其連接到一起，如果某一個子串 s 是它們的公共子串，則 s 一定會在連接后字符串后綴數(shù)組中出現(xiàn)兩次，這樣就將最長公共子串轉成最長重復子串的問題了，這里的后綴數(shù)組我們使用基本的實現(xiàn)方式。

值得一提的是，在找到兩個重復子串時，不一定就是 X 與 Y 的公共子串，也可能是 X 或 Y 的自身重復子串，故在連接時候我們在 X 后面插入一個特殊字符‘#’，即連接后為 X#Y。這樣一來，只有找到的兩個重復子串恰好有一個在 #的前面，這兩個重復子串才是 X 與 Y 的公共子串

設字符串 X 的長度為 m，Y 的長度為 n，最長公共子串長度為 l。

對于基本算法（brute force），X 的子串（m 個）和 Y 的子串（n 個）一一對比，最壞情況下，復雜度為 O(m*n*l)，空間復雜度為 O(1)。

對于 DP 算法，由于自底向上構建最優(yōu)子問題的解，時間復雜度為 O(m*n)；空間復雜度為 O(m*n)，當然這里是可以使用滾動數(shù)組來優(yōu)化空間的，滾動數(shù)組在動態(tài)規(guī)劃基礎回顧中多次提到。

對于后綴數(shù)組方法，連接到一起并初始化后綴數(shù)組的時間復雜度為 O(m+n)，對后綴數(shù)組的字符串排序，由于后綴數(shù)組有 m+n 個后綴子串，子串間比較，故復雜度為 O((m+n)*l*lg(m+n))，求得最長子串遍歷后綴數(shù)組，復雜度為 O(m+n)，所以總的時間復雜度為 O((m+n)*l*lg(m+n))，空間復雜度為 O(m+n)。

總的來說使用后綴數(shù)組對數(shù)據(jù)做一些 “預處理”，在效率上還是能提升不少的。

問題描述：找出一個n個數(shù)的序列的最長單調遞增子序列： 比如A = {5,6,7,1,2,8} 的LIS是5,6,7,8

1.1 最優(yōu)子結構：
LIS[i] 是以arr[i]為末尾的LIS序列的長度。則：
LIS[i] = {1+Max(LIS(j))}; j;
LIS[i] = 1, j, 但是不存在arr[j];
所以問題轉化為計算Max(LIS(j)) 0

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }

import java.util.*;

public class LIS {
    public static int lengthofLCS(int[] arr){
        // 輔助變量
        int[] MaxV = new int [arr.length+1]; // 記錄遞增子序列 LIS 的末尾元素最小值 
        int nMaxLength = 1; // 當前LIS的長度
        int [] LIS = new int[arr.length+1]; //LIS[i]記錄的是以第i個元素為結尾的最長序列的長度
        // 初始化
        MaxV[0] = -100;
        MaxV[nMaxLength] = arr[0];
        LIS[0] = 0;LIS[1] = 1;

        for(int i=1;iMaxV[nMaxLength]){
                MaxV[++nMaxLength] = arr[i];
                LIS[i] = LIS[i-1]+1;
            }
            else{
                // 新元素 更小，更有“潛力”，替換大的元素
                int index = binarySearch(MaxV,arr[i],0,nMaxLength);     
                //*     
                LIS[i] =index;
                MaxV[index] = arr[i];
            }
        }
        Arrays.sort(LIS);
        return LIS[LIS.length-1];
    }
    // 在MaxV數(shù)組中查找一個元素剛剛大于arr[i]
    // 返回這個元素的index
    public static int binarySearch(int []arr, int n, int start, int end){
        while(start n) {
                end = mid -1;
            }
            else 
                return mid;
        }
        return end;
    }
    public static void main(String[] args) {
        int[] arr = {2,1,5,3,6,4,8,9,7};
        System.out.println(lengthofLCS(arr));
    }

}