Subsequence - 演算法筆記

二維陣列length[i][j] ，代表「 s1 前i 個元素」和「 s2 前j 個元素」的LCS 長度。

... 中央橫排，找到最大值位置，分成左上區與右下區，遞迴縮小問題。

LongestCommonSubsequence LongestCommonSubsequence（LCS） 「最長共同子序列」。

出現於每一個序列、而且是最長的子序列。

可能有許多個。

s1:2579312 s2:35328 LCS(s1,s2)=532 s1:abcdbceea s2:cabdefga s3:dcea LCS(s1,s2,s3)={cea,dea} 求出兩個序列的LCS，P問題。

接下來將介紹各種演算法。

求出一群序列的LCS，NP-hard問題，沒有快速的演算法。

簡單的方式是窮舉法：窮舉s1的所有子序列，檢查s2...sN是否都有該子序列。

時間複雜度O(s1!⋅(s2+...+sN))。

LongestCommonSubsequence:DynamicProgramming 演算法（Needleman–WunschAlgorithm） 削減尾端元素，遞迴縮小問題。

s1和s2的最後一個元素，叫做e1和e2，拆解出來。

s1=sub1+e1 s2=sub2+e2 四種情況： 一、LCS包含e1不含e2：LCS(s1,s2)=LCS(s1,sub2) 二、LCS不含e1包含e2：LCS(s1,s2)=LCS(sub1,s2) 　　（e1毫無用處，想找LCS只需要找sub1。

） 三、LCS不含e1e2：LCS(s1,s2)=LCS(sub1,sub2) 四、LCS包含e1e2：LCS(s1,s2)=LCS(sub1,sub2)+e1 　　（LCS的最後一個元素一定是e1，也等於e2。

） 遞迴公式： LCS(s1,s2)= {max(LCS(sub1,s2),LCS(s1,sub2),LCS(sub1,sub2)) {whene1≠e2 {LCS(sub1,sub2)+e1whene1=e2 簡化： LCS(s1,s2)= {max(LCS(sub1,s2),LCS(s1,sub2))whene1≠e2 {LCS(sub1,sub2)+e1whene1=e2 初始值： LCS(s1,s2)=Øwhens1=Øors2=Ø 時間複雜度O(NM)，空間複雜度O(NM)。

N和M是序列長度。

©2010tkcn.Allrightsreserved. 計算LongestCommonSubsequence的長度 二維陣列length[i][j]，代表「s1前i個元素」和「s2前j個元素」的LCS長度。

有個節省記憶體空間的方法。

填表格，只需要上格、左格、左上格。

計算順序，設定為從左往右、再從上往下，如此只需要一條陣列（上排）、以及一個數值（左上格）。

長序列為直向，短序列為橫向，陣列長度最短。

空間複雜度降為O(min(N,M))。

constintN1=7,N2=5; //為了實作方便，從陣列的第1格開始存入序列。

ints1[N1+1]={0,2,5,7,9,3,1,2}; ints2[N2+1]={0,3,5,3,2,8}; intlength[N1+1][N2+1]; //DP表格 intLCS() { //初始值：當s1或s2是空集合，則LCS是空集合。

for(inti=0;i<=N1;i++)length[i][0]=0; for(intj=0;j<=N2;j++)length[0][j]=0; //填表格：依照遞迴公式 for(inti=1;i<=N1;i++) for(intj=1;j<=N2;j++) if(s1[i]==s2[j]) length[i][j]=length[i-1][j-1]+1; else length[i][j]=max(length[i-1][j], length[i][j-1]); returnlength[N1][N2]; } 找出一個LongestCommonSubsequence 使用一個二維陣列，記錄每一格的結果是從哪一格而來。

往回追溯，每當發現某一格length[i][j]是由length[i-1][j-1]+1而來，就印出s1[i]（也是s2[j]）。

有個節省記憶體空間的方法。

只計算LCS長度。

填表格，自頂往中央，自底往中央，相遇於中央，將答案相加。

中央橫排，找到最大值位置，分成左上區與右下區，遞迴縮小問題。

遞迴下去的區域，只佔半個表格。

整個遞迴過程，1+(1/2)+(1/4)+(1/8)+...≤2，只佔兩個表格。

時間複雜度升為兩倍。

空間複雜度降為O(N+M)。

constintN1=7,N2=5; ints1[N1+1]={0,2,5,7,9,3,1,2}; ints2[N2+1]={0,3,5,3,2,8}; intlength[N1+1][N2+1]; //DP表格 intprev[N1+1][N2+1]; //記錄每一格的的結果是從哪一格而來 intlcs[min(N1,N2)]; voidLCS() { for(inti=0;i<=N1;i++)length[i][0]=0; for(intj=0;j<=N2;j++)length[0][j]=0; for(inti=1;i<=N1;i++) for(intj=1;j<=N2;j++) if(s1[i]==s2[j]) { length[i][j]=length[i-1][j-1]+1; prev[i][j]=0; //左上格 } else { if(length[i-1][j]0) if(prev[i][j]==0) //左上格 l--,lcs[l]=s1[i]; elseif(prev[i][j]==1) //左格 j--; elseif(prev[i][j]==2) //上格 i--; l=length[i][j]; for(inti=0;i 找出所有的LongestCommonSubsequence 填表格的時候，LCS可能同時來自上格、左格、左上格，將這些情形全部記錄下來。

往回追溯的時候，將這些情形通通追溯一遍，求出所有LCS。

LCS數量最多O(2ᴺ)個。

UVa11153110066101921040510723 演算法（Hirschberg'sAlgorithm） 表格分割成左上區、右下區，遞迴縮小問題。

前面已介紹。

時間複雜度O(NM)。

空間複雜度O(N+M)。

演算法（Four-RussiansSpeedup） 表格切割成小方塊，小方塊直接查表。

小方塊邊長logN/4。

時間複雜度O(N²/logN)。

不無小補。

LongestCommonSubsequence:Hunt–SzymanskiAlgorithm LCS問題化作二維LIS問題 兩序列找出相同元素，表示成位置數對。

兩序列的LCS＝位置數對的2DLIS。

(1)LCSproblem: index:0123456789 -------------------------- s1:abacd s2:dbaabca (2)matchedpositions: dbaabca +---------------aaabb a|***(0,2)(0,3)(0,6)(1,1)(1,4) b|** a|***aaacd c|*(2,2)(2,3)(2,6)(3,5)(4,0) d|* (3-1){LCS==2DLIS}example: dbaabca +--------------- a|x**LCS:aba b|*x2DLIS:(0,2)(1,4)(2,6) a|**x c|*數對呈嚴格遞增，在表格中則是往右下走。

d|* (3-2){LCS==2DLIS}anotherexample: dbaabca +--------------- a|***LCS:bac b|x*2DLIS:(1,1)(2,2)(3,5) a|x** c|x數對呈嚴格遞增，在表格中則是往右下走。

d|* 二維LIS問題化作一維LIS問題 排序所有數對：第一維由小到大排序；當第一維平手，則第二維由大到小排序。

排序之後，原本數對們的2DLIS＝第二維的1DLIS。

(1)sortallpairs: aaabbaaacd (0,6)(0,3)(0,2)(1,4)(1,1)(2,6)(2,3)(2,2)(3,5)(4,0) increasingin1stcomponents. thendecreasingin2ndcomponents. (2)2ndcomponents: 6324163250 (3){2DLIS==1DLIS}example: 6324163250 *** LCS:aba 2DLIS:(0,2)(1,4)(2,6) 1DLIS:246 (4)allinone: abacds1 ->{a(6,3,2)b(4,1)a(6,3,2)c(5)d(0)}sortedmatchedpositions ->{6324163250}2ndcomponent ->246LIS 演算法 LCS問題，化作2DLIS問題，再化作1DLIS問題，最後套用Robinson–Schensted–KnuthAlgorithm。

排序所有數對，使用CountingSort。

掃描一遍s2，把每個字元的位置紀錄下來。

較短的序列當作s1，時間複雜度是O(Klog(min(N,M))+R)。

K是數對數目，N和M是序列長度，R是數字範圍。

K至多是NM，最差情況下比先前的演算法還慢，平均情況下比先前的演算法快上許多。

R源自CountingSort。

計算LongestCommonSubsequence的長度 intLCS(vector&s1,vector&s2) { // if(s1.size()==0||s2.size()==0)return0; /*CountingSort*/ vectorp[128]; //假設字元範圍為0~127 for(inti=0;i=0;--j) { intn=p[s1[i]][j]; if(n>v.back()) v.push_back(n); else *lower_bound(v.begin(),v.end(),n)=n; } returnv.size()-1; } UVa1063510949 LIS問題與LCS問題可以互相轉換 LIS轉LCS：令原序列A排序後變成B。

A和B的LCS，就是A的LIS。

LCS轉LIS：將序列A和B當中的相同字母配對通通找出來，表示成位置數對，以特殊規則排序，然後找到LIS，就是A和B的LCS。

LongestCommonIncreasingSubsequence LongestCommonIncreasingSubsequence（LCIS） 嚴格遞增的LCS。

LCS的DP演算法稍作修改，隨時找到最有潛力的LCIS。

時間複雜度仍是O(NM)。

421423142142314214231 +---------------+---------------+--------------- 1|**1|x*1|x* 2|**2|*x2|*x 4|**4|**4|** 3|*3|x3|* 4|**4|**4|** allmatchedpairsLCISbest-candidateLCIS whenvisitpair(3,3) constintN1=5,N2=7; ints1[N1]={1,2,4,3,4}; ints2[N2]={4,2,1,4,2,3,1}; intlength[N1]; //精簡成一維陣列 intprev[N1][N2]; intlcis[min(N1,N2)]; voidLCIS() { memset(prev,-1,sizeof(prev)); //初始化為-1 for(inti=0;il) l=length[j],p=j; } } //計算LCIS長度、尾端位置 intl=0,p=-1; for(inti=0;il) l=length[i],p=i; //找出一個LCIS for(inti=N1-1,j=p,k=l;k>0;--i) if(prev[i][j]!=-1) { lcis[--k]=s2[j]; j=prev[i][j]; } cout<