病毒的dna剖析一道字符匹配問題解析過程

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

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

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

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

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

6、比較類似一般字符匹配問題，不同點在于此題有環(huán)串存在！,求解的變換,如果最長公共部分長度大于等于N,那么此公共部分中包含C中所有字符。,∵如果最大公共部分的長度小于N的，直接可輸出0。,∴ 我們只需考慮最大公共長度大于等于N的情況。,那么如果求出從B的第i位和C的第一位起向后循環(huán)匹配的最大長度,記為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)匹配的最大長度，記為L[i-1]。,R[i]的求解,R[i]的初步求法為： 枚舉B中位置i，和C向后匹配到不能匹配為止，顯然匹配的長度可達到M，那么此法的復雜度為O(M2)，復雜度有增無減！ 必須考慮避免不必要的匹配:,如果從I開始往后逐字比較時，已匹配的

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

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

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

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

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

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

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