基于位運(yùn)算的最長(zhǎng)公共子串算法

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

2、的公共子串的最大可能長(zhǎng)度。例如，字符集S=’A’’C’’G’’T’，’GCTAT’和’CGATTA’的最大公共子串（以下簡(jiǎn)稱(chēng)LCS）為’GTT’，其長(zhǎng)度為3。在這里定義一些變量:AB分別是兩個(gè)給定的串。S為A、B串所涉及的字符集。[常規(guī)動(dòng)態(tài)規(guī)劃算法常規(guī)動(dòng)態(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、)[基于位運(yùn)算的動(dòng)態(tài)規(guī)劃算法基于位運(yùn)算的動(dòng)態(tài)規(guī)劃算法]根據(jù)上面的動(dòng)態(tài)規(guī)劃算法，狀態(tài)函數(shù)L具有如下性質(zhì)：L[i1j1]≤L[ij1]L[i1j]≤L[ij]|L[ij]L[i1j1]|≤1對(duì)于L的每一行，相鄰的兩個(gè)元素的最多只相差1。這樣一來(lái)，我們就可以用一個(gè)二進(jìn)制的矩陣描述出L:()1..[][]kjLijMik???IOI2006國(guó)家集訓(xùn)隊(duì)作業(yè)：研究報(bào)告浙江唐文斌每一段都是從Row[i1]的一個(gè)1的位開(kāi)始往右延伸，直到下一個(gè)位置是1或

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

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

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

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