最長公共子序列演算法利用

A. 求數組的最大子數組值和最長公共子序列問題

a) 最長公共子序列的結構
若用窮舉搜索法，耗時太長，演算法需要指數時間。
易證最長公共子序列問題也有最優子結構性質
設序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一個最長公共子序列Z=<z1, z2, …, zk>，則：
i. 若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；
ii. 若xm≠yn且zk≠xm ，則Z是Xm-1和Y的最長公共子序列；
iii. 若xm≠yn且zk≠yn ，則Z是X和Yn-1的最長公共子序列。
其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
最長公共子序列問題具有最優子結構性質。

B. 最長公共子序列的應用

最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的「相似度」，即它們的雷同程度，從而能夠用來辨別抄襲。對一段文字進行修改之後，計算改動前後文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分准確。簡而言之，網路知道、網路都用得上。

C. 動態規劃 最長公共子序列 過程圖解

首先需要科普一下，最長公共子序列（longest common sequence）和最長公共子串（longest common substring）不是一回事兒。

這里給出一個例子：有兩個母串
cnblogs
belong
比如序列bo, bg, lg在母串cnblogs與belong中都出現過並且出現順序與母串保持一致，我們將其稱為公共子序列。最長公共子序列（Longest Common Subsequence,LCS），顧名思義，是指在所有的子序列中最長的那一個。

子串是要求更嚴格的一種子序列， 要求在母串中連續地出現 。
在上述例子的中，最長公共子序列為blog（cnblogs,belong），最長公共子串為lo（cnblogs, belong）。

給一個圖再解釋一下：

如上圖，給定的字元序列： {a,b,c,d,e,f,g,h}，它的子序列示例： {a,c,e,f} 即元素b,d,g,h被去掉後，保持原有的元素序列所得到的結果就是子序列。同理，{a,h},{c,d,e}等都是它的子序列。
它的子串示例：{c,d,e,f} 即連續元素c,d,e,f組成的串是給定序列的子串。同理，{a,b,c,d},{g,h}等都是它的子串。

這個問題說明白後，最長公共子序列（以下都簡稱LCS）就很好理解了。
給定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}，s1和s2的相同子序列，且該子序列的長度最長，即是LCS。
s1和s2的其中一個最長公共子序列是 {3,4,6,7,8}

求解LCS問題，不能使用暴力搜索方法。 一個長度為n的序列擁有 2的n次方個子序列，它的時間復雜度是指數階 ，太恐怖了。解決LCS問題，需要藉助動態規劃的思想。

動態規劃演算法通常用於求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應於一個值，我們希望找到具有最優值的解。動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重復計算了很多次。 為了避免大量的重復計算，節省時間，我們引入一個數組，不管它們是否對最終解有用，把所有子問題的解存於該數組中，這就是動態規劃法所採用的基本方法。

解決LCS問題，需要把原問題分解成若干個子問題，所以需要刻畫LCS的特徵。

設A=「a0，a1，…，am」，B=「b0，b1，…，bn」，且Z=「z0，z1，…，zk」為它們的最長公共子序列。不難證明有以下性質：
如果am=bn，則zk=am=bn，且「z0，z1，…，z(k-1)」是「a0，a1，…，a(m-1)」和「b0，b1，…，b(n-1)」的一個最長公共子序列；
如果am!=bn，則若zk!=am，蘊涵「z0，z1，…，zk」是「a0，a1，…，a(m-1)」和「b0，b1，…，bn」的一個最長公共子序列；
如果am!=bn，則若zk!=bn，蘊涵「z0，z1，…，zk」是「a0，a1，…，am」和「b0，b1，…，b(n-1)」的一個最長公共子序列。

有些同學，一看性質就容易暈菜，所以我給出一個圖來讓這些同學理解一下：

以我在第1小節舉的例子（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}），並結合上圖來說：

假如S1的最後一個元素 與 S2的最後一個元素相等，那麼S1和S2的LCS就等於 {S1減去最後一個元素} 與 {S2減去最後一個元素} 的 LCS 再加上 S1和S2相等的最後一個元素。

假如S1的最後一個元素 與 S2的最後一個元素不等（本例子就是屬於這種情況），那麼S1和S2的LCS就等於 ： {S1減去最後一個元素} 與 S2 的LCS， {S2減去最後一個元素} 與 S1 的LCS 中的最大的那個序列。

假設Z=<z1,z2,⋯,zk>是X與Y的LCS， 我們觀察到
如果Xm=Yn，則Zk=Xm=Yn，有Zk−1是Xm−1與Yn−1的LCS；
如果Xm≠Yn，則Zk是Xm與Yn−1的LCS，或者是Xm−1與Yn的LCS。

因此，求解LCS的問題則變成遞歸求解的兩個子問題。但是，上述的遞歸求解的辦法中， 重復的子問題多，效率低下。改進的辦法——用空間換時間，用數組保存中間狀態，方便後面的計算。這就是動態規劃（DP)的核心思想了。
DP求解LCS
用二維數組c[i][j]記錄串x1x2⋯xi與y1y2⋯yj的LCS長度，則可得到狀態轉移方程

以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}為例。我們借用《演算法導論》中的推導圖：

圖中的空白格子需要填上相應的數字（這個數字就是c[i,j]的定義，記錄的LCS的長度值）。填的規則依據遞歸公式，簡單來說：如果橫豎（i,j）對應的兩個元素相等，該格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化該表：

S1的元素3 與 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])，圖中c[1,2] 和 c[2,1] 背景色為淺黃色。

繼續填充：

至此，該表填完。根據性質，c[8,9] = S1 和 S2 的 LCS的長度，即為5。

本文S1和S2的最LCS並不是只有1個，本文並不是著重講輸出兩個序列的所有LCS，只是介紹如何通過上表，輸出其中一個LCS。

我們根據遞歸公式構建了上表，我們將從最後一個元素c[8][9]倒推出S1和S2的LCS。

c[8][9] = 5，且S1[8] != S2[9]，所以倒推回去，c[8][9]的值來源於c[8][8]的值(因為c[8][8] > c[7][9])。

c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去，c[8][8]的值來源於 c[7][7]。

以此類推，如果遇到S1[i] != S2[j] ，且c[i-1][j] = c[i][j-1] 這種存在分支的情況，這里請都選擇一個方向（之後遇到這樣的情況，也選擇相同的方向）。

這就是倒推回去的路徑，棕色方格為相等元素，即LCS = {3,4,6,7,8}，這是其中一個結果。

如果如果遇到S1[i] != S2[j] ，且c[i-1][j] = c[i][j-1] 這種存在分支的情況，選擇另一個方向，會得到另一個結果。

即LCS ={3,5,7,7,8}。

構建c[i][j]表需要Θ(mn)，輸出1個LCS的序列需要Θ(m+n)。

參考：
https://blog.csdn.net/hrn1216/article/details/51534607
https://blog.csdn.net/u012102306/article/details/53184446

D. C語言實現最長公共子串與最長公共子序列

給定兩個字元串s1="GeeksforGeeks"，s2="GeeksQuizGo"，則它們的最長公共子串為「Geeks」，長度為5。

運用動態規劃的思想，將兩個字元串映射為一張二維表，表格中的值代表到當前為止的最長公共子串的值，如下圖所示：

生成這張表的步驟（假設這張表為t[][], r為行標，c為列標）：

Code

整個演算法的時間復雜度為O(len1 * len2)，len1與len2分別為兩個字元串的長度。

最長公共子序列與最長公共子串的區別是，最長公共子序列不要求「連續匹配」，它的目的是找到兩個字元串中最大的公共部分。依然以s1="GeeksforGeeks"，s2="GeeksQuizGo"為例，它們的最長公共子序列為「Geekso」和「GeeksG」，長度為6。

它的二維表如下所示：

它的生成步驟與最長公共子序列的最大不同在第3步，最長公共子序列在遇到s1[r] != s2[c]情況時，不會將t[r][c]重置為0，而是選擇Max(t[r-1][c], t[r][c-1])作為新值，即它一直保存著前面已比較序列的最長公共序列值。