基于位運算的最長公共子串算法

1、IOI2006國家集訓(xùn)隊作業(yè)：研究報告浙江唐文斌基于位運算的最長公共子串算法浙江唐文斌[摘要摘要]本文來自于參考文獻[1]。本文描述了一個對于確定有限字符集的基于位運算的最長公共子串算法。該算法在普通計算機上運行效率明顯高于常規(guī)的動態(tài)算法。其時間復(fù)雜度為。其中(||||)OAwB????w表示我們在w位的整數(shù)上進行位操作。[問題介紹問題介紹]最長公共子串（LongestcommonsubsequenceLCS）問題，是求兩個字符串A和B

2、的公共子串的最大可能長度。例如，字符集S=’A’’C’’G’’T’，’GCTAT’和’CGATTA’的最大公共子串（以下簡稱LCS）為’GTT’，其長度為3。在這里定義一些變量:AB分別是兩個給定的串。S為A、B串所涉及的字符集。[常規(guī)動態(tài)規(guī)劃算法常規(guī)動態(tài)規(guī)劃算法]設(shè)L[ij]等于A[1..i]B[1..j]的LCS.則有L[ij]=1L[i1j1]如果(A[i]=B[j])Max(L[i1j]L[ij1])其他復(fù)雜度為O(|A||B|

3、)[基于位運算的動態(tài)規(guī)劃算法基于位運算的動態(tài)規(guī)劃算法]根據(jù)上面的動態(tài)規(guī)劃算法，狀態(tài)函數(shù)L具有如下性質(zhì)：L[i1j1]≤L[ij1]L[i1j]≤L[ij]|L[ij]L[i1j1]|≤1對于L的每一行，相鄰的兩個元素的最多只相差1。這樣一來，我們就可以用一個二進制的矩陣描述出L:()1..[][]kjLijMik???IOI2006國家集訓(xùn)隊作業(yè)：研究報告浙江唐文斌每一段都是從Row[i1]的一個1的位開始往右延伸，直到下一個位置是1或

4、者串結(jié)束。如果Row[i1]的最左邊的位置上是0，那么最左邊的一段從B[i]string的最左邊的1的位置開始延伸直到下一個1。Row[i]的構(gòu)成方式很簡單：就是對于每一段，都是選擇Row[i1]或者B[i]string最右邊的1所在位置為1，其他的為0。如果這一段Row[i1]和B[i]string都是0，那么Row[i]這一段也為0?！甌’stringRow[10]:1101100110011111Row[11]:000010001

5、0011111表示了進行或操作之后每一段最右邊的1附帶一提，你可以假定在每個串的最左邊（位置|A|1）存在一個1，這樣可以方便處理最左邊一段全為0的情況。不過對于本算法并沒有這個必要。在Row[i1]中的一個1的位置，代表了A中的一個最短前綴與B[1..i1]的LCS達到了該長度。引進B[i]，最好的方法當(dāng)然是在前面的最短基礎(chǔ)上加入一個最短的與B[i]的匹配，也就是從那個1所在的位置往左找，找到的第一個能與B[i]匹配的(如果找得到的話

6、)。設(shè)X=Row[i1]B[i]string對于當(dāng)前的例子，X=Row[10]‘T’stringX:1101100110011111把Row[i1]往左移1位，并且設(shè)最低位為1，用X去減這個串：X:110110011001111100000010001111111101011101100000這個操作所表達的意思為對于每一段，把最右邊的一個1變成0，把這個1右邊的所有0變成1，設(shè)最低位為1的目的是為了可以同樣處理最后一段。再跟X進行X(

7、異或)操作，得到：0000111011111111這步操作之后的結(jié)果就是，對于每一段，從最右邊的1開始到段尾變成1，其他變成0。因為X為1當(dāng)且僅當(dāng)兩個位上的數(shù)不同，而上一次操作我們修改過的位是從最右邊的1直到段尾。接下來就很顯然了，只要再將上面的結(jié)果與X進行操作即可。得到：0000100010011111這樣就得到了Row[i]即當(dāng)前例子中的Row[11]。綜上，Row[i]=X((X–((Row[i1]1)1))XX)其中X=Row[