字符串算法集合

1、字符串相關(guān)算法字符串相關(guān)算法 KMP（KMP和擴展和擴展KMP） Trie樹樹 AC自動機自動機 Trie圖圖 Suffix Array(后綴數(shù)組）后綴數(shù)組） 字符串字符串HASH(Rabin Karp、 ELF Hash) 字符串循環(huán)最小表示字符串循環(huán)最小表示 BM(Boyer-Moore)算法算法目目錄錄KMPKMP算法算法簡介 KMP算法是用于處理字符串匹配的高效算法 給定兩個字符串，判斷B串是否是A串的子串（即A串是否包含B串） 在一個長字符串中匹配一個短子串的無回溯算法樸素算法 枚舉A串中的每個字符，將起作為起點，將其與B串中的字符進行一一比較 For (I = 0 ; i strl

2、en(A); I +) For ( j = 0 ; j strlen(B); j +) if (Bj!=Ai+j) break; if (j=strlen(B) return yes; 復雜度 設(shè)A串（主串）長度為n，B串（模式串、匹配串）長度為m 樸素算法為枚舉A串的每個字符為起點看是否包含B串，復雜度為O（m * n） KMP算法復雜度O（m + n） KMP工作過程 用兩個指針i和j分別表示，Ai-j+ 1.i與B1.j完全相等 i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以Ai結(jié)尾的長度為j的字符串正好匹配B串的前 j個字符 KMP工作過程 Ai+1 = Bj+1 ，i + ，j

3、 + Ai+1 != Bj+1 ，j減小，i不變，使得出現(xiàn)新的j，滿足Ai結(jié)尾的長度為j的字符串正好匹配B串的前 j個字符 這時匹配的字符的個數(shù)已減少，相當于位置的移動KMP工作過程 例 1 2 3 4 5 6 7 8 9 A = a b a b a b a a b a b B = a b a b a c b 1 2 3 4 5 6 當i = 5 ， j = 5時，出現(xiàn)Ai+1 != Bj+1 ，j應(yīng)當變小，從而實現(xiàn)新的匹配KMP工作過程 此時，A6B6。這表明，此時j不能等于5了，我們要把j改成比它小的值j。j可能是多少呢？仔細想一下，我們發(fā)現(xiàn)，j必須要使得B1.j中的頭j個字母和末j個字母

4、完全相等（這樣j變成了j后才能繼續(xù)保持i和j的性質(zhì)）。 KMP工作過程 例 1 2 3 4 5 6 7 8 9 A = a b a b a b a a b a b B = a b a b a c b 1 2 3 4 5 6 j由5變?yōu)?，使得A35與B13匹配，然后再按照剛才算法繼續(xù)執(zhí)行KMP工作過程 定義next數(shù)組記錄當在j位置出現(xiàn)不匹配的時候j應(yīng)該改變的值，當出現(xiàn)不匹配的時候令j = nextj; 設(shè)A串長度為lena，B串長度為lenb，則整個計算過程如下：偽代碼 for (i = j = 0; i lena & j lenb; ) if(j 0 | Ai = Bj)i +, j +;

5、elsej = nextj; Next從何而來 Next數(shù)組很好很強大，可是它要怎么來呢？ 直觀的看，j應(yīng)該是能滿足Ai結(jié)尾的長度為j的字符串正好匹配B串的前 j個字符的盡量大的值 實際上，B串建立next的過程和主串尋找匹配的過程是一樣的Next數(shù)組的含義設(shè)nexti=j這意味著對于串B來說B1B2Bj=Bi-j+1BjNext尋找過程 如果Bk = Bj，k j，則可以令nextj +1 = k + 1，否則另k = nextk，然后再看新的Bk和Bj是否匹配 令最初的next0 = -1作為入口，則建立next的過程如下Next尋找過程 int j = 0, t = next0 = -1

6、; while(j lenb - 1) if(t 0 | Bj = Bt)next+ j = + t;elset = nextt; 百科名片 KMP算法是通過分析子串，預先計算每個位置發(fā)生不匹配的時候，所需GOTO的下一個比較位置，整理出來一個next數(shù)組，然后在上面的算法中使用。 ProblemPKU 2185 給出一個字母組成的矩陣，找出一個最小的子矩陣，使得這個子矩陣的無限復制擴張之后的矩陣包含原來的矩陣，例如 ABABA ABABA 其最小重復子矩陣是ABl解法求出每一行的最小重復串長度，所有行的最小重復串的長度的lcm就是最小重復子矩陣的寬；求出每一列的最小重復串長度，所有列的最小重

7、復串的長度的lcm就是最小重復子矩陣的長。l最小重復串長度？利用KMP得到P數(shù)組串長-末位的P值擴展的擴展的KMPKMP算法算法樊向宇樊向宇【擴展的【擴展的KMP算法】算法】擴展的擴展的KMPKMP問題：問題：給定母串S，和子串T。 定義n=|S|, m=|T|，extendi=Si.n與T的最長公共前綴長度。請在線性的時間復雜度內(nèi)，求出所有的extend1.n。容易發(fā)現(xiàn)，如果有某個位置i滿足extendi=m，那么T就肯定在S中出現(xiàn)過，并且進一步知道出現(xiàn)首位置是i而這正是經(jīng)典的KMP問題。 因此可見“擴展的KMP問題”是對經(jīng)典KMP問題的一個擴充和加難。 例子 S=aaaaaaaaaabaa

8、a, T=aaaaaaaaaaa。extend2=9。為了計算extend2，我們是不是也要進行10次比較運算呢？不然。因為通過計算extend1=10，我們可以得到這樣的信息： S1.10=T1.10 S2.10=T2.10。計算extend2的時候，實際上是S2開始匹配T。因為S2.10=T2.10，所以在匹配的開頭階段是“以T2.10為母串，T為子串”的匹配。 設(shè)輔助函數(shù)nexti表示Ti.m與T的最長公共前綴長度。 對上述例子，next2=10。也就是說： T2.11=T1.10 T2.10=T1.9 S2.10=T1.9。這就是說前9位的比較是完全可以避免的！我們直接從S11T10開

9、始比較。這時候一比較就發(fā)現(xiàn)失配，因此extend2=9。 下面提出一般的算法。 設(shè)extend1.k已經(jīng)算好，并且在以前的匹配過程中到達的最遠位置是p。最遠位置嚴格的說就是i+extendi-1的最大值，其中i=1,2,3,k；不妨設(shè)這個取最大值的i是a。(下圖黃色表示已經(jīng)求出來了extend的位置)第一種情況第一種情況第二種情況第二種情況 整個算法描述結(jié)束。 上述算法是線性線性算法。原因如下： 容易看出，在計算的過程中，凡是訪問過的點，都不需要重新訪問了。一旦比較，都是比較以前從不曾探訪過的點開始。因此總的時間復雜度是O(n+m),是線性的。如何求解如何求解next數(shù)組數(shù)組還剩下一個問題：n

10、ext這個輔助數(shù)組怎么計算？復雜度是多少？我們發(fā)現(xiàn)計算next實際上以實際上以T為母串、為母串、T為子串的一個特殊為子串的一個特殊“擴展的擴展的KMP”。用上文介紹的完全相同的算法計算next即可。（用next本身計算next，具體可以參考標準KMP）此不贅述。總結(jié)總結(jié) 算法的思想 已經(jīng)訪問過的點絕不再訪問，充分利用已經(jīng)訪問過的點絕不再訪問，充分利用已經(jīng)得到的信息。已經(jīng)得到的信息。擴展擴展KMP的一些應(yīng)用的一些應(yīng)用 求解最長公共前綴長度 求字符串中重復子串的長度 （利用next數(shù)組，nexti表示Ti.m與T的最長公 共前綴長度。 找重復子串 ，比如abababccc ，ababab就是重復子

11、串；再比如 ababa，這個也是重復的，只是最后一個循環(huán)節(jié)不完整，端點處的循環(huán)節(jié)不完整的串也算作重復串。 因此i+nexti的長度就是重復子串的長度。） 例如poj2185 比如ababab ，next2 = 4， 2，3匹配0，1 ；然后4，5匹配2，3；相當于還是匹配0，1 ；所以0，1被重復了3次，所以只要是能匹配上的，就是在重復前i個字符 ，能匹配多長，就是重復了多長，直接用i+nexti就是最長的長度 。求解extend數(shù)組的模板void GetExtand(const EleType str, int strLen, int extand, const EleType mode,

12、int modeLen, int next) int i, a, p, j(-1); for (i = 0; i strLen; +i, -j) if (j = p) if (j 0) j = 0, p = i; while (p strLen & j modeLen & strp = modej) +p, +j; extandi = j, a = i; else extandi = nexti - a; 根據(jù)上面的模板，大家可以仿照寫計算next的函數(shù)。 poj2185主要求解next數(shù)組，唯一的不同在于此題是一個二維char數(shù)組，我們可以先把每一列看作一個點，這樣整個二維數(shù)組看成一個字符串

13、，算出nexti;在把每一行看作一個點，又一個字符串，再求出一組nexti。這兩個過程中，分別對求出來的nexti,根據(jù)i+nexti=len（表示循環(huán)長度覆蓋了整個串），進行判斷篩選，將行與列的結(jié)果進行組合，即求得可行解。（題目要求的是面積）TRIETRIE樹樹樊向宇樊向宇Trie樹 字典樹 空間換時間 引入問題：對于包含100000個長度不超過10的單詞組成的字典庫，給定任意一個單詞，判斷其是否為字典庫中某個單詞的前綴 給定b，abc，abd，bcd，abcd，efg，hii，建立Trie樹如下結(jié)點Struct nodeint nextMAX_N; /指向子節(jié)點bool end;/標記單詞

14、末尾Problem 現(xiàn)有4000個單詞組成的詞庫，每個單詞長度不超過100。給定一字符串，長度不超過300000，要求將字符串分割為詞庫中的單詞，問有多少種方法。 Sampleabcd ans=24abcdabACAC自動機自動機樊向宇樊向宇AC自動機 設(shè)共有設(shè)共有m個模式串，長度分別為個模式串，長度分別為L1、L2Lm正文為一個長度為正文為一個長度為n的數(shù)組的數(shù)組T1.n，限定，限定900Kn,1000m,100KL樸素算法 從小到大枚舉每一個位置，并且對所有模式從小到大枚舉每一個位置，并且對所有模式串進行檢查。最壞情況下時間復雜度為串進行檢查。最壞情況下時間復雜度為 對每一個模式串，使用對

15、每一個模式串，使用kmp算法進行單串匹算法進行單串匹配，時間復雜度為配，時間復雜度為)Ln(O)Lmn(O前綴指針 KMP中我們用兩個指針i和j分別表示，Ai-j+ 1.i與B1.j完全相等。也就是說，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以Ai結(jié)尾的長度為j的字符串正好匹配B串的前 j個字符，當Ai+1Bj+1，KMP的策略是調(diào)整j的位置（減小j值）使得Ai-j+1.i與B1.j保持匹配且新的Bj+1恰好與Ai+1匹配（從而使得i和j能繼續(xù)增加）。 Trie樹上的前綴指針與此類似。假設(shè)有一個節(jié)點k，他的前綴指針指向j。那么k,j滿足這個性質(zhì)：設(shè)root到j(luò)的距離為n，則從k之上的

16、第n個節(jié)點到k所組成的長度為n的單詞，與從root到j(luò)所組成的單詞相同。生成前綴指針 root及其兒子的前綴指針指向root 對于每個節(jié)點：設(shè)這個節(jié)點上的字母為C，沿著他父親的前綴指針走，直到走到一個節(jié)點，他的兒子中也有字母為C的節(jié)點。然后把當前節(jié)點的前綴指針指向那個字母也為C的兒子。如果一直走到了root都沒找到，那就把前綴指針指向root BFS匹配過程初始Trie中有一個指針t1指向root，待匹配串中有一個指針t2指向串頭。接下來的操作和KMP很相似：如果t2指向的字母，是Trie樹中，t1指向的節(jié)點的兒子，那么t2+1,t1改為那個兒子的編號，否則t1順這當前節(jié)點的前綴指針向上找，直

17、到t2是t1的一個兒子，或者t1指向根。如果t1路過了一個綠色的點，那么以這個點結(jié)尾的單詞就算出現(xiàn)過了?；蛘呷绻鹴1所在的點可以順著前綴指針走到一個綠色點，那么以那個綠點結(jié)尾的單詞就算出現(xiàn)過了。 注意傳遞性注意傳遞性自上至下標記自上至下標記zababaabcbabaaabaProblem 給定10000個長度不超過50的關(guān)鍵詞，對于一長度不超過1000000的字符串，求其中出現(xiàn)了多少種關(guān)鍵詞？TrieTrie圖圖樊向宇樊向宇Trie圖 Trie圖是AC自動機的擴展，每個節(jié)點對于字符集中的所有字符均存在一個指針 建圖流程建立Trie 樹生成前綴指針補齊所有邊 前綴節(jié)點的求法與AC自動機相同 補邊

18、的方法為： 從根結(jié)點出發(fā)的補邊指向根本身； 對非根結(jié)點x，若它沒有c孩子，則新建一條邊，從x指向x的后綴結(jié)點的c孩子。 處理某個結(jié)點的過程中需要用到深度比它小的結(jié)點的后綴結(jié)點及各個孩子。由于我們按層次遍歷trie樹，這些信息都已求得。Trie圖的構(gòu)建（構(gòu)建流程演示）結(jié)點前綴a孩子b孩子c孩子001491012924573391049405795112669104974578891049901049101129501942107863abcbcaccba圖例：安全結(jié)點危險結(jié)點cbcabababacabcProblem 給出n(n=10)個長度不超過的惡性DNA片段，要求構(gòu)造長度為m(m=2000

19、000000)的DNA序列，使其不包含惡性DNA片段，求構(gòu)造方法總數(shù)Sample Input4 3ATACAGAASample Output36Problem DNA Repair給出n(1=n=50）個長度不超過20的惡性DNA片段，對于一個長度為m(1=m=1000)的DNA序列，通過改變最少的字符使其不包含惡性片段。Sample Input2AAA AAG AAAGSample Output1Suffix Suffix ArrayArray( (后綴數(shù)組）后綴數(shù)組）樊向宇樊向宇后綴數(shù)組 對字符串的所有后綴按字典序排序，將各后綴的起始位置按排序后的順序擺放得到后綴數(shù)組SA。 RANK數(shù)組與

20、SA相對應(yīng)，Ranki保存Suffix(i)在排序中的名次SA構(gòu)造方法 倍增算法 DC3算法倍增算法對字符串u，定義uk =u1.k,len(u)ku ,len(u)k定義k-前綴比較關(guān)系k，=k和k對兩個字符串u,v，ukv當且僅當ukvku=kv當且僅當uk=vkukv當且僅當ukvk倍增算法uvukv？u=kv？ukv？kuvu2kv？u=2kv？u2kv？kk后綴數(shù)組構(gòu)造方法設(shè)u=Suffix(i)，v=Suffix(j)后綴u，以i開頭后綴v，以j開頭對u、v在2k-前綴意義下進行比較kkkk比較紅色字符相當于在k-前綴意義下比較Suffix(i) 和 Suffix(j)比較綠色字符

21、相當于在k-前綴意義下比較Suffix(i+k) 和 Suffix(j+k)在2k-前綴意義下比較兩個后綴可以轉(zhuǎn)化成在k-前綴意義下比較兩個后綴i+kj+k后綴數(shù)組構(gòu)造方法把n個后綴按照k-前綴意義下的大小關(guān)系從小到大排序?qū)⑴判蚝蟮暮缶Y的開頭位置順次放入數(shù)組SAk中，稱為k-后綴數(shù)組用Rankki保存Suffix(i)在排序中的名次，稱數(shù)組Rankk為k-名次數(shù)組后綴數(shù)組構(gòu)造方法利用SAk可以在O(n)時間內(nèi)求出Rankk利用Rankk可以在常數(shù)時間內(nèi)對兩個后綴進行k-前綴意義下的大小比較后綴數(shù)組構(gòu)造方法如果已經(jīng)求出Rankk可以在常數(shù)時間內(nèi)對兩個后綴進行k-前綴意義下的比較可以在常數(shù)時間內(nèi)對

22、兩個后綴進行2k-前綴意義下的比較可以很方便地對所有的后綴在2k-前綴意義下排序采用快速排序O(nlogn)采用基數(shù)排序O(n)可以在O(n)時間內(nèi)由Rankk求出SA2k也就可以在O(n)時間內(nèi)求出Rank2k 后綴數(shù)組構(gòu)造方法1-前綴比較關(guān)系實際上是對字符串的第一個字符進行比較可以直接根據(jù)開頭字符對所有后綴進行排序求出SA1采用快速排序，復雜度為O(nlogn)然后根據(jù)SA1在O(n)時間內(nèi)求出Rank1可以在可以在O(nlogn)時間內(nèi)求出時間內(nèi)求出SA1和和Rank1后綴數(shù)組構(gòu)造方法直接根據(jù)首字符排序SA1Rank1O(nlogn)SA2Rank2O(n)SA4Rank4O(n)SA8

23、Rank8O(n)O(n)SAmRankmO(n)m=2t且mnO(nlogn)的操作一次O(n)的操作logn次總復雜度為O(nlogn)后綴數(shù)組輔助工具僅僅靠后綴數(shù)組和名次數(shù)組有時候還不能很好地處理問題后綴數(shù)組的最佳搭檔LCP定義兩個字符串的最長公共前綴Longest Common Prefixlcp(u,v)=maxi|u=iv也就是從頭開始比較u和v的對應(yīng)字符持續(xù)相等的最遠值后綴數(shù)組輔助工具定義LCP(i,j)=lcp(Suffix(SAi),Suffix(SAj)也就是SA數(shù)組中第i個和第j個后綴的最長公共前綴LCP Theorem對任何1i1 且Ranki1，一定有hihi-1-1

24、后綴數(shù)組輔助工具當hi-11 時，hi0hi-1-1。當hi-11時，令j=i-1,k=SARankj-1。顯然有Suffix(k)1 和Suffix(k)Suffix(j)：lcp(Suffix(k+1),Suffix(i)=hi-1-1。Rankk+1wj+k，同理可以討論ui+kwj+(x-i)j+k。1ixu：i+ki+k+1 |s1|1w：jj+(x-i)j+kj+k+1 |s2|大于s1(x-1)的前幾個字符一定是s1的其他循環(huán)表示的前幾個字符所以s1(x-1)不可能是s1的最小表示！因此M(s1)i+k，指針i滑到ui+k+1處仍可以保證小于等于M(s1)！“最小表示法”在本題的應(yīng)用同理，當ui+kwj+k的時候，可以將指針j滑到wj+k+1處！也就是說，兩指針向后滑動比較失敗以