病毒的dna剖析一道字符匹配問(wèn)題解析過(guò)程

1、病毒的DNA—剖析一道字符匹配問(wèn)題解析過(guò)程,長(zhǎng)沙長(zhǎng)郡中學(xué) 饒向榮,——,題目描述,有一種奇特的病毒，它的DNA序列是環(huán)狀的，而一般的生物的DNA都是線狀的，且由科學(xué)家發(fā)現(xiàn)：生物被此種病毒侵襲的可能性與生物和病毒的DNA序列最大公共長(zhǎng)度有關(guān)，由于病毒是環(huán)狀的，所以它可以循環(huán)重復(fù)的匹配?？茖W(xué)家們經(jīng)過(guò)大量的試驗(yàn)發(fā)現(xiàn)：如果生物和病毒DNA序列的最大公共部分的長(zhǎng)度還沒(méi)有病毒的DNA長(zhǎng)，病毒是無(wú)法安身的，也就是說(shuō)這個(gè)生物被侵染的幾率是0，否則，最

2、長(zhǎng)公共部分的長(zhǎng)度和被侵染的幾率滿足下面的關(guān)系式： 生物被侵染幾率=最大公共部分長(zhǎng)度 / 生物DNA長(zhǎng)度。任務(wù) 現(xiàn)在已知病毒的DNA序列和某生物的DNA序列，你必須求出此生物被侵染的幾率是多少。,題目描述,數(shù)據(jù)范圍 病毒的DNA序列長(zhǎng)度〈=1000，生物DNA序列長(zhǎng)度〈=105。樣例 病毒的DNA序列(環(huán)狀)為abc，生物的DNA序列為abbcabcabb,那么它們的

3、最長(zhǎng)的公共長(zhǎng)度為7，最長(zhǎng)公共部分為紅色部分：bcabcab。,分析和求解,設(shè)A為病毒的環(huán)狀DNA字串，A的長(zhǎng)度為N。 設(shè)B為生物的線狀DNA字串，B的長(zhǎng)度為M。 那么題目所求：環(huán)串A和線串B的最大可循環(huán)公共子串長(zhǎng)度。,設(shè)f [i, j] 表示以線串B的第i位和環(huán)串A的第j位結(jié)尾的最大公共子串的長(zhǎng)度。,根據(jù)平時(shí)的解題經(jīng)驗(yàn)，很容易想到用動(dòng)態(tài)規(guī)劃來(lái)解此類求公共最大長(zhǎng)度的題目，而且稍加分析就可設(shè)計(jì)相應(yīng)的動(dòng)態(tài)規(guī)劃：,分析和求解,最后的

4、答案：,空間復(fù)雜度為O(N)。,那么動(dòng)態(tài)轉(zhuǎn)移方程：,分析和求解,經(jīng)過(guò)分析，不必求出依次所有的f [i, j] ，只有當(dāng)B[i]=A[j]時(shí)，才有必要求f [i, j]，其余的f值全為0。 又因?yàn)锳,B中的字符只有[‘a(chǎn)’..’z’,’A’..’Z’]，那么只需在開(kāi)始時(shí)用鏈表記錄‘a(chǎn)’..’z’,’A’..’Z’出現(xiàn)的位置,動(dòng)態(tài)規(guī)劃的過(guò)程中就可以實(shí)現(xiàn)這個(gè)優(yōu)化。,優(yōu)化：,時(shí)間復(fù)雜度：O(M*N)。n<=1000, m<

5、;=105。,時(shí)間復(fù)雜度 太高了！,分析和求解,很難找到在時(shí)間復(fù)雜度上有質(zhì)的飛躍的其它的動(dòng)態(tài)規(guī)劃。,問(wèn)題的結(jié)癥沒(méi)有解決：,是否有其他的更好的動(dòng)態(tài)規(guī)劃！,算法的時(shí)間復(fù)雜度還是沒(méi)有降低。,問(wèn)題轉(zhuǎn)化,只有最大公共子串的長(zhǎng)度大于等于N時(shí)，才有必要計(jì)算這個(gè)長(zhǎng)度。,,因?yàn)榄h(huán)串的匹配起始位置是不定的，與一般的字符匹配問(wèn)題是不同的。所以不妨先將環(huán)串A斷開(kāi)，設(shè)為線串C。,動(dòng)態(tài)規(guī)劃未用到另一條件:,如何運(yùn)用此條件？,轉(zhuǎn)換思路，又可以發(fā)現(xiàn)：此題實(shí)際上

6、比較類似一般字符匹配問(wèn)題，不同點(diǎn)在于此題有環(huán)串存在！,求解的變換,如果最長(zhǎng)公共部分長(zhǎng)度大于等于N,那么此公共部分中包含C中所有字符。,∵如果最大公共部分的長(zhǎng)度小于N的，直接可輸出0。,∴ 我們只需考慮最大公共長(zhǎng)度大于等于N的情況。,那么如果求出從B的第i位和C的第一位起向后循環(huán)匹配的最大長(zhǎng)度,記為R[i]。,abc,abbcabcabb,,,,R[i],L[i-1],B[i],,B[i-1],abbcabcabb,abbcabcabb,

7、abbcabcabb,abbcabcabb,abbcabcabb,abbcabcabb,abbcabcabb,=5,2=,再求出從B的第i-1位和C的最后一位起向前循環(huán)匹配的最大長(zhǎng)度，記為L(zhǎng)[i-1]。,R[i]的求解,R[i]的初步求法為： 枚舉B中位置i，和C向后匹配到不能匹配為止，顯然匹配的長(zhǎng)度可達(dá)到M，那么此法的復(fù)雜度為O(M2)，復(fù)雜度有增無(wú)減！ 必須考慮避免不必要的匹配:,如果從I開(kāi)始往后逐字比較時(shí)，已匹配的

8、長(zhǎng)度已經(jīng)達(dá)到了N，那么就沒(méi)有必要再往后比較了，必然有R[i]=R[i+n]+n成立。,abbcabcabb,R[i],R[i+n],,n,abc,abbcabcabb,abbcabcabb,Q[i]的求解,定義Q[i]表示B從位置i開(kāi)始和C非循環(huán)匹配的最大長(zhǎng)度。那么求出Q[i]，就求出了R[i]了。,R[i]那么問(wèn)題等價(jià)于求Q[i]，如何求Q[i]? 一般的，到了這一步，我們希望可以通過(guò)字符匹配類問(wèn)題中高效的KMP算法來(lái)求出Q[

9、i]。 但稍加分析就會(huì)發(fā)現(xiàn):KMP的匹配過(guò)程是跳動(dòng)的，不便于求出所有的Q[i]。,分析和求解,雖然直接運(yùn)用KMP求Q[i]的計(jì)劃落空，但是否還可以借鑒KMP的解題思路和特點(diǎn)來(lái)設(shè)計(jì)Q[i]的求法呢？ 首先，要使復(fù)雜度盡量低，總的匹配次數(shù)也就應(yīng)該盡量少。而KMP解題的一大特點(diǎn)就是：盡量的利用了前面的比較結(jié)果，達(dá)到了不重復(fù)比較被匹配串中已匹配字符的目的。 在Q[i]的計(jì)算上是否也可以做到這一點(diǎn)呢？,ab

10、bcabcabb,abc,abbcabcabb,abbcabcabb,K為求Q[1..i-1]的過(guò)程中, B中已被匹配到最大的位置。 J為匹配到K的起始位置。,,,,,,分析和求解,為了不重復(fù)比較B中已匹配字符，最理想的情況下，我們期望可以直接從k+1位開(kāi)始向后比較就能求出Q[i]。,顯然，如果能直接確定Q[i]+i>=k時(shí)，也就是從i位置起，可匹配到的最大位置不小于k，就可以直接從k+1位開(kāi)始往后逐字比較求Q[i]

11、。,但這樣就存在兩個(gè)問(wèn)題： 1. 怎么確定Q[i]+i>=k呢？2. 如果Q[i]+i<k時(shí)，又怎么辦呢？,KMP算法達(dá)到避免重復(fù)比較目的的關(guān)鍵點(diǎn)在于： 將匹配串和被匹配串對(duì)應(yīng)起來(lái)考慮。,分析和求解,先考慮B串中j到k這一段。顯然它和C串的1到k-j+1這段是完全一樣的；同樣，B中的i位置，對(duì)應(yīng)于C串中的i-j+1位置。,分析和求解,求出從C的第i-j+1位和C的第一位開(kāi)始可匹配的最大長(zhǎng)度，記為L(zhǎng)。,

12、,L,dcdcdccbcabc,分析和求解,觀察上圖，可得出以下結(jié)論：當(dāng)L=k-i+1時(shí)：Q[i]+i>=k。只需從k+1向后逐字比較，就可求出Q[i]。,,k-i+1,所以，關(guān)鍵在L的計(jì)算上。,分析和求解,L的值僅由i-j+1和C確定。設(shè)T[x](1<=x<=n)，表示從C的x位置起和C匹配的最大長(zhǎng)度。那么求解R的過(guò)程中，對(duì)B中任何位置i和對(duì)應(yīng)的j，T[i-j+1]就相當(dāng)于要求的L。,=T[i - j+1]

13、,T的求解,接下來(lái)，求解T: 其實(shí)T的計(jì)算和Q的計(jì)算本質(zhì)上是一樣：都要求從一個(gè)字串的每個(gè)位置起和C可匹配的最大長(zhǎng)度。 Q[i]可通過(guò)T[1..n]和適當(dāng)比較算出來(lái)，而T[x]則可通過(guò)T[1..x-1]和適當(dāng)?shù)谋容^求出來(lái)。那么計(jì)算T[x]的時(shí)間復(fù)雜度：O(N)。,復(fù)雜度分析,此算法的總時(shí)間復(fù)雜度=匹配的時(shí)間復(fù)雜度+計(jì)算T[x]的時(shí)間復(fù)雜度=O(M+N)。,效率上得到了極大的提高。 問(wèn)題圓滿解決

14、！,上面的解決方式，看起來(lái)與KMP十分的相似，但實(shí)際上透徹的理解后，還是有很大的區(qū)別的。此解法主要是借鑒KMP的思想和特點(diǎn)提出的，而不是生搬硬套。,回顧解題過(guò)程,下面回顧整個(gè)解題的過(guò)程：,1.先考慮動(dòng)態(tài)規(guī)劃，行不通！,2.分析問(wèn)題，發(fā)現(xiàn)問(wèn)題要求長(zhǎng)度不小于N的公共部分，這是此題 轉(zhuǎn)化的關(guān)鍵條件。,3.求解分解為L(zhǎng)[i]和R[i] 。,4.精簡(jiǎn)R[i]的求解，求相應(yīng)的Q[i]。,5.靈活運(yùn)用KMP解題思路和特點(diǎn)，設(shè)計(jì)出T數(shù)組,使得匹配的時(shí)間