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

2、此生物被侵染的幾率是多少。,題目描述,數(shù)據(jù)范圍 病毒的DNA序列長度=1000，生物DNA序列長度=105。 樣例 病毒的DNA序列(環(huán)狀)為abc，生物的DNA序列為abbcabcabb,那么它們的最長的公共長度為7，最長公共部分為紅色部分：bcabcab。,分析和求解,設(shè)A為病毒的環(huán)狀DNA字串，A的長度為N。 設(shè)B為生物的線狀DNA字串，B的長度為M。 那么題目所求：環(huán)串A和線串B的最大可循環(huán)公共子串長度。,設(shè)f i, j 表示以線串B的第i位和環(huán)串A的第j位結(jié)尾的最大公共子串的長度。,根據(jù)平時的解題經(jīng)驗，很容易想到用動態(tài)規(guī)劃來解此類求公共最大長度的題目，而且稍加分析就可設(shè)計相應(yīng)的動態(tài)規(guī)

3、劃：,分析和求解,最后的答案：,空間復(fù)雜度為O(N)。,那么動態(tài)轉(zhuǎn)移方程：,分析和求解,經(jīng)過分析，不必求出依次所有的f i, j ，只有當Bi=Aj時，才有必要求f i, j，其余的f值全為0。 又因為A,B中的字符只有a.z,A.Z，那么只需在開始時用鏈表記錄a.z,A.Z出現(xiàn)的位置,動態(tài)規(guī)劃的過程中就可以實現(xiàn)這個優(yōu)化。,優(yōu)化：,時間復(fù)雜度：O(M*N)。n=1000, m=105。,時間復(fù)雜度 太高了！,分析和求解,很難找到在時間復(fù)雜度上有質(zhì)的飛躍的其它的動態(tài)規(guī)劃。,問題的結(jié)癥沒有解決：,是否有其他的更好的動態(tài)規(guī)劃！,算法的時間復(fù)雜度還是沒有降低。,問題轉(zhuǎn)化,只有最大公共子串的長度大于等于

4、N時，才有必要計算這個長度。,因為環(huán)串的匹配起始位置是不定的，與一般的字符匹配問題是不同的。所以不妨先將環(huán)串A斷開，設(shè)為線串C。,動態(tài)規(guī)劃未用到另一條件:,如何運用此條件？,轉(zhuǎn)換思路，又可以發(fā)現(xiàn)：此題實際上比較類似一般字符匹配問題，不同點在于此題有環(huán)串存在！,求解的變換,如果最長公共部分長度大于等于N,那么此公共部分中包含C中所有字符。,如果最大公共部分的長度小于N的，直接可輸出0。, 我們只需考慮最大公共長度大于等于N的情況。,那么如果求出從B的第i位和C的第一位起向后循環(huán)匹配的最大長度,記為Ri。,abc,abbcabcabb,Ri,Li-1,Bi,Bi-1,abbcabcabb,abbc

5、abcabb,abbcabcabb,abbcabcabb,abbcabcabb,abbcabcabb,abbcabcabb,=5,2=,再求出從B的第i-1位和C的最后一位起向前循環(huán)匹配的最大長度，記為Li-1。,Ri的求解,Ri的初步求法為： 枚舉B中位置i，和C向后匹配到不能匹配為止，顯然匹配的長度可達到M，那么此法的復(fù)雜度為O(M2)，復(fù)雜度有增無減！ 必須考慮避免不必要的匹配:,如果從I開始往后逐字比較時，已匹配的長度已經(jīng)達到了N，那么就沒有必要再往后比較了，必然有Ri=Ri+n+n成立。,abbcabcabb,Ri,Ri+n,n,abc,abbcabcabb,abbcabcabb,Q

6、i的求解,定義Qi表示B從位置i開始和C非循環(huán)匹配的最大長度。那么求出Qi，就求出了Ri了。,Ri那么問題等價于求Qi，如何求Qi? 一般的，到了這一步，我們希望可以通過字符匹配類問題中高效的KMP算法來求出Qi。 但稍加分析就會發(fā)現(xiàn):KMP的匹配過程是跳動的，不便于求出所有的Qi。,分析和求解,雖然直接運用KMP求Qi的計劃落空，但是否還可以借鑒KMP的解題思路和特點來設(shè)計Qi的求法呢？ 首先，要使復(fù)雜度盡量低，總的匹配次數(shù)也就應(yīng)該盡量少。而KMP解題的一大特點就是：盡量的利用了前面的比較結(jié)果，達到了不重復(fù)比較被匹配串中已匹配字符的目的。 在Qi的計算上是否也可以做到這一點呢？,abbcab

7、cabb,abc,abbcabcabb,abbcabcabb,K為求Q1.i-1的過程中, B中已被匹配到最大的位置。 J為匹配到K的起始位置。,分析和求解,為了不重復(fù)比較B中已匹配字符，最理想的情況下，我們期望可以直接從k+1位開始向后比較就能求出Qi。,顯然，如果能直接確定Qi+i=k時，也就是從i位置起，可匹配到的最大位置不小于k，就可以直接從k+1位開始往后逐字比較求Qi。,但這樣就存在兩個問題： 1. 怎么確定Qi+i=k呢？ 2. 如果Qi+ik時，又怎么辦呢？,KMP算法達到避免重復(fù)比較目的的關(guān)鍵點在于： 將匹配串和被匹配串對應(yīng)起來考慮。,分析和求解,先考慮B串中j到k這一段。顯

8、然它和C串的1到k-j+1這段是完全一樣的；同樣，B中的i位置，對應(yīng)于C串中的i-j+1位置。,分析和求解,求出從C的第i-j+1位和C的第一位開始可匹配的最大長度，記為L。,L,dcdcdccbcabc,分析和求解,觀察上圖，可得出以下結(jié)論： 當L=k-i+1時：Qi+i=k。只需從k+1向后逐字比較，就可求出Qi。,k-i+1,所以，關(guān)鍵在L的計算上。,分析和求解,L的值僅由i-j+1和C確定。 設(shè)Tx(1=x=n)，表示從C的x位置起和C匹配的最大長度。 那么求解R的過程中，對B中任何位置i和對應(yīng)的j，Ti-j+1就相當于要求的L。,=Ti - j+1,T的求解,接下來，求解T: 其實T

9、的計算和Q的計算本質(zhì)上是一樣：都要求從一個字串的每個位置起和C可匹配的最大長度。 Qi可通過T1.n和適當比較算出來，而Tx則可通過T1.x-1和適當?shù)谋容^求出來。 那么計算Tx的時間復(fù)雜度：O(N)。,復(fù)雜度分析,此算法的總時間復(fù)雜度 =匹配的時間復(fù)雜度+計算Tx的時間復(fù)雜度 =O(M+N)。,效率上得到了極大的提高。 問題圓滿解決！,上面的解決方式，看起來與KMP十分的相似，但實際上透徹的理解后，還是有很大的區(qū)別的。此解法主要是借鑒KMP的思想和特點提出的，而不是生搬硬套。,回顧解題過程,下面回顧整個解題的過程：,1.先考慮動態(tài)規(guī)劃，行不通！,2.分析問題，發(fā)現(xiàn)問題要求長度不小于N的公共部分，這是此題 轉(zhuǎn)化的關(guān)鍵條件。,3.求解分解為Li和Ri 。,4.精簡Ri的求解，求相應(yīng)的Qi。,5.靈活運用KMP解題思路和特點，設(shè)計出T數(shù)組,使得匹配的時間復(fù)雜度降為O(M)。這部分是圓滿解決此問題的關(guān)鍵。,總結(jié),上面Qi的求解思路具有一定的可推