關于字符串處理中兩個問題討論

1、關于字符串處理中的兩個問題的討論中國地質科學院 鄒偉 2014年5月25日最長公共子序列和最長回文串的搜索LCS的定義最長公共子序列，即Longest Common Subsequence，LCS。其定義是，一個序列 S ，如果分別是兩個已知序列的子序列，且是所有子序列中最長的，則 S 稱為這兩個已知序列的最長公共子序列。字符串13455與245576的最長公共子序列為455字符串acdfg與akdfc的最長公共子序列為adf注意與最長公共子串（Longest Common Substring）的區(qū)別LCS的意義求兩個序列中最長的公共子序列算法，廣泛的應用在圖形相似處理、媒體流的相似比較、計算

2、生物學方面。生物學家常常利用該算法進行基因序列比對，由此推測序列的結構、功能和演化過程。LCS可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來辨別抄襲。另一方面，對一段文字進行修改之后，計算改動前后文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準確。簡而言之，百度知道、百度百科都用得上。LCS的解法窮舉法動態(tài)規(guī)劃法Hirschberg/Nakatsu算法窮舉法假定字符串X，Y的長度分別為m，n；對X的每一個子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過程中選出最長的公共子序列；X的一個子序列即下標序列1,

3、 2, , m的嚴格遞增子序列，因此，X共有2m個不同子序列；同理，Y有2n個不同子序列，從而窮舉搜索法需要指數(shù)時間O(2m . 2n)；顯然，不可取。LCS的記號字符串X，長度為m，從1開始數(shù)；字符串Y，長度為n ，從1開始數(shù)；Xi=x1，xi即X序列的前i個字符 (1im)（Xi不妨讀作“字符串X的i前綴”） Yj=y1，yj即Y序列的前j個字符 (1jn) （字符串Y的j前綴）；LCS(X , Y) 為字符串X和Y的最長公共子序列，即為Z=z1，zk。不嚴格的表述。事實上，X和Y的可能存在多個子串，長度相同并且最大，因此，LCS(X,Y)嚴格的說，是個字符串集合。即：Z LCS(X ,

4、Y) .LCS解法的探索若xm=yn（最后一個字符相同），則可以得到：X與Y的最長公共子序列Z（設長度為k）的最后一個字符必定為xm(=yn)，即有zk = xm = yn 且顯然有Zk-1=LCS(Xm-1 , Yn-1)即Z的前綴Zk-1是Xm-1與Yn-1的最長公共子序列。LCS(X , Y) = LCS(Xm-1 , Yn-1) + xmZk = Zk-1 + xm反證法LCS解法的探索若xmyn，則得到：要么Zk=LCS(Xm-1, Y)，要么Zk=LCS(X , Yn-1)。原因：zkxm與zkyn其中至少有一個必成立，若zkxm則有Zk=LCS(Xm-1 , Y)，類似的，若zk

5、yn 則有Zk=LCS(X , Yn-1)。LCS(X , Y) = maxLCS(Xm-1 , Y), LCS(X , Yn-1) 所謂LCS(X,Y) LCS(A,B)，定義為LCS(X,Y)的長度大于LCS(A,B)的長度LCS解法的探索若能夠計算如下三個問題，則LCS(X,Y)迎刃而解：LCS(Xm-1, Yn-1) s.t. xm=ynLCS(Xm-1, Y) / LCS(X, Yn-1) s.t. xm ynmaxLCS(Xm-1, Y), LCS(X, Yn-1)顯然，屬于動態(tài)規(guī)劃問題。 總結如下設序列X=和Y=的一個最長公共子序列Z=，則：若xm=yn，則zk=xm=yn且Zk

6、-1是Xm-1和Yn-1的最長公共子序列；若xmyn且zkxm ，則Zk是Xm-1和Y的最長公共子序列；若xmyn且zkyn ，則Zk是X和Yn-1的最長公共子序列；算法中的數(shù)據(jù)結構使用二維數(shù)組Cm,n；（note：X長度為m，Y長度為n）ci,j記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=，Yj=。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故ci,j=0。方向變量使用二維數(shù)據(jù)Bm,n，其中，bi,j標記ci,j的值是由哪一個子問題的解達到的。即ci,j是由ci-1,j-1+1或者ci-1,j或者ci,j-1的哪一個得到的。取值范圍為Left，Top，LeftTop三種情

7、況。計算LCS長度的偽代碼Procedure LCS_LENGTH(X,Y); begin m:=lengthX; n:=lengthY; for i:=1 to m do ci,0:=0; for j:=1 to n do c0,j:=0; for i:=1 to m do for j:=1 to n do if xi=yj then begin ci,j:=ci-1,j-1+1; bi,j:=; end else if ci-1,jci,j-1 then begin ci,j:=ci-1,j; bi,j:=; end else begin ci,j:=ci,j-1; bi,j:= end;

8、 return(c,b); end; 根據(jù)b提供的方向，構造最長公共子序列Procedure LCS(b,X,i,j); begin if i=0 or j=0 then return; if bi,j= then begin LCS(b,X,i-1,j-1); print(xi); /打印xi end else if bi,j= then LCS(b,X,i-1,j) else LCS(b,X,i,j-1); end; 實例X=Y=三點改進在算法LCS_LENGTH和LCS中，可進一步將數(shù)組b省去。事實上，數(shù)組元素ci,j的值僅由ci-1,j-1，ci-1,j和ci,j-1三個值之一確定，而

9、數(shù)組元素bi,j也只是用來指示ci,j究竟由哪個值確定。因此，在算法LCS中，我們可以不借助于數(shù)組b而借助于數(shù)組c本身臨時判斷ci,j的值是由ci-1,j-1，ci-1,j和ci,j-1中哪一個數(shù)值元素所確定，代價是(1)時間。既然b對于算法LCS不是必要的，那么算法LCS_LENGTH便不必保存它。這一來，可節(jié)省 (mn)的空間，而LCS_LENGTH和LCS所需要的時間分別仍然是(mn)和(m+n)。不過，由于數(shù)組c仍需要(mn)的空間，因此這里所作的改進，只是在空間復雜性的常數(shù)因子上的改進。 另外，如果只需要計算最長公共子序列的長度，則算法的空間需求還可大大減少。事實上，在計算ci,j時

10、，只用到數(shù)組c的第i行和第i-1行。因此，只要用2行的數(shù)組空間就可以計算出最長公共子序列的長度。更進一步的分析還可將空間需求減至min(m, n)。求所有最大公共子序列，而不僅僅是其中一個X=Y=LCS：BCAB / BCBA求所有最大公共子序列B的取值范圍從1,2,3擴展到1,2,3,4廣度優(yōu)先遍歷Hirschberg/Nakatsu算法子序列(Subsequence)：給定字符串A=A1A2Am，(Ai是A 的第i 個字母，Ai字符集，l= im = A ， A 表示字符串A 的長度)，字符串B 是A 的子序列是指B=A 1 i A 2 i A k i ,其中1 i 2 i k i 且k=

11、m. 公共子序列(Common Subsequence)：給定字符串A、B、C，C 稱為A 和B 的公共子序列是指C 既是A 的子序列，又是B 的子序列。最長公共子序列(Longest Common Subsequence 簡稱LCS)：給定字符串A、B、C，C 稱為A 和B 的最長公共子序列是指C 是A 和B 的公共子序列，且對于A 和B 的任意公共子序列D，都有D = C 。給定字符串A 和B的長度記為m、n，不妨設m=n。給定字符串A=A1A2Am和字符串B=B1B2n，A( 1:i)表示A 的連續(xù)子序列A1A2Ai，同樣B(1:j)表示B 的連續(xù)子序列B1B2j。Li(k)表示所有與字

12、符串A(1:i) 有長度為k 的LCS 的字符串B(l:j) 中j 的最小值。用公式表示就是Li(k)=Minj(LCS(A(1:i)，B(l:j)=k)。 考察定義4關于Li(k)的簡要結論根據(jù)Li(k)的定義，得到以下結論算法實現(xiàn)Demo實用：最長遞增子序列LISLongest Increasing Subsequence給定一個長度為N的數(shù)組，找出一個最長的單調遞增子序列（不一定連續(xù)，但是順序不能亂）。例如：給定一個長度為6的數(shù)組A5， 6， 7， 1， 2， 8，則其最長的單調遞增子序列為5，6，7，8，長度為4。分析：其實此LIS問題可以轉換成最長公子序列問題，為什么呢？使用LCS解

13、LIS問題原數(shù)組為A 5， 6， 7， 1， 2， 8排序后：A1， 2， 5， 6， 7， 8因為，原數(shù)組A的子序列順序保持不變，而且排序后A本身就是遞增的，這樣，就保證了兩序列的最長公共子序列的遞增特性。如此，若想求數(shù)組A的最長遞增子序列，其實就是求數(shù)組A與它的排序數(shù)組A的最長公共子序列。此外，本題也可以直接使用動態(tài)規(guī)劃來求解附：LIS的動態(tài)規(guī)化算法設長度為N的數(shù)組為a0，a1, a2, .an-1，則假定以aj結尾的數(shù)組序列的最長遞增子序列長度為L(j)，則L(j)= max(L(i)+1, ij且aiaj 。也就是說，我們需要遍歷在j之前的所有位置i(從0到j-1)，找出滿足條件aia

14、j的L(i)，求出max(L(i)+1即為L(j)的值。最后，我們遍歷所有的L(j)（從0到N-1），找出最大值即為最大遞增子序列。時間復雜度為O(N2)。附：LIS求字符串的最長回文子串回文子串的定義：給定字符串str，若s同時滿足以下條件：s是str的子串s是回文串則，s是str的回文子串。該算法的要求，是求str中最長的那個回文子串。解法1 枚舉中心位置int LongestPalindrome(const char *s, int n) int i, j, max; if (s = 0 | n 1) return 0; max = 0; for (i = 0; i = 0) & (i

15、+ j max) max = j * 2 + 1; for (j = 0; (i - j = 0) & (i + j + 1 max) max = j * 2 + 2; return max;解法2線性時間解決問題(Manachers ALGORITHM)void pk() int i; int mx = 0; int id; for(i=1; i i ) pi = MIN( p2*id-i, mx-i ); else pi = 1; for(; stri+pi = stri-pi; pi+); if( pi + i mx ) mx = pi + i; id = i; 算法解析 step1預處

16、理因為回文串有奇數(shù)和偶數(shù)的不同。判斷一個串是否是回文串，往往要分開編寫，造成代碼的拖沓。一個簡單的事實：長度為n的字符串，共有n-1個“鄰接”，加上首字符的前面，和末字符的后面，更n+1的“空”(gap)。因此，字符串本身和gap一起，共有2n+1個，必定是奇數(shù)；abbc #a#b#b#c#aba #a#b#a#因此，將待計算母串擴展成gap串，計算回文子串的過程中，只考慮奇數(shù)匹配即可。數(shù)組int Psize字符串12212321 S = $#1#2#2#1#2#3#2#1#;用一個數(shù)組 Pi 來記錄以字符Si為中心的最長回文子串向左/右擴張的長度（包括Si），比如S和P的對應關系：S # 1

17、 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1Pi-1正好是原字符串中回文串的總長度對代碼初步的理解void pk() int i; int mx = 0; int id; for(i=1; i i ) pi = MIN( p2*id-i, mx-i ); else pi = 1; for(; stri+pi = stri-pi; pi+); if( pi + i mx ) mx = pi + i; id = i; MIN的理解當 mx - i Pj 的時候，以Sj為中心的回文子串包含在以Sid為中心的回文子串中，由于 i 和 j 對稱，以Si為中心的回文子串必然包含在以Sid為中心的回文子串中，所以必有 Pi = Pj：MIN的理解當 Pj = mx - i 的時候，以Sj為中心的回文子串不一定完全包含于以Sid為中心的回文子串中，但是基于對稱性可知，下圖中兩個綠框所包圍的部分是相同的，也就是說以Si為中心的回文子串，其向右至少會擴張到mx的位置，也就是說 Pi = m