最長公共子序列問題實驗報告（最長公共子序列）

大家好，我是小夏，我來為大家解答以上問題。最長公共子序列問題實驗報告，最長公共子序列很多人還不知道，現在讓我們一起來看看吧！

1、這里要說的這個算法利用了nlogn的最長上升子序列(LIS)的技巧：用f[k]表示長度為k的上升子序列最后一個數最小是多少。

2、 在最長公共上升子序列中，令f[i,j][k]表示A串前i個數字，B串前j個數字，長度為k的公共上升子序列中，最后一個數最小是多少。

3、 當A[i]=B[j]時，像nlogn的最長上升子序列一樣把A[i]插入到f[i-1,j]中，這需要線性的時間掃一遍f[i,j]；

4、 當A[i]<>B[j]時，我們需要合并f[i-1,j]和f[i,j-1]，使得對于每個k滿足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。這需要線性的時間掃一邊f[i-1,j]和f[i,j-1]并取k相同時的較小值。

5、 最后輸出f[n,m]的長度（使f[n,m][k]有意義的最大的k）。

6、 這樣的復雜度是三方的，我們需要優化。

7、 考慮A[i]=B[j]的情況。當i固定時，隨著j的增加，插入的位置一定也在后移，因為同樣是插入的A[i]，但j的增加（B串長度的增加）使得f [i,j]更優，因此可以更新的值就更靠后。于是，對于每個i，我們可以按照k的順序掃描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置時增加j，從而預處理所有A[i]=B[j]時A[i]應該插入的位置。

8、 再考慮A[i]<>B[j]的情況。從定義看，f[i-1,j-1]和f[i-1,j]只有一個地方不一樣，因為多一個數最多只能造成一個k 的值變小；同樣地，f[i-1,j-1]和f[i,j-1]也只有一個地方不一樣。因此，f[i-1,j]和f[i,j-1]最多只有兩個k所對應的值不相同，且當有兩個不同的值時，總是f[i-1,j]中的某個值較小，f[i,j-1]中的某個值較小。這給我們優化的余地。在每次處理完f[i,j]時，我們可以記錄一個值x[i,j]表示f[i,j][k]與f[i-1,j][k]中值不一樣的k是多少，在A[i]=B[j]時直接賦值為插入的位置，在 A[i]<>B[j]時待后文說明。以后合并時，先讓f[i,j]:=f[i-1,j]（由于此時的f[i-1,j]已經沒有別的用處了，因此可以用滾動數組記錄，直接令f[i-1,j]是f[i,j]，避免實際的賦值操作），然后將新的f[i,j]中的，使f[i,j-1][k]比f[i- 1, j][k]小的k所對應值更新。這個k是多少呢？顯然應該是x[i,j-1]。這樣的操作同時可以確定x[i,j]=x[i,j-1]。

9、 這樣，復雜度就達到了平方。

10、 附參考的資料（原來從這篇論文里學到的，不知道有沒有此類的中文資料，估計沒有才在這里寫了一個，感興趣的話可以下載附件仔細研究）

11、引自M67的博客： http://www.matrix67.com/blog/?s=LCIS

本文到此講解完畢了，希望對大家有幫助。