|
時(shí)間：最初寫于2011年12月,，2014年7月21日晚10點(diǎn) 全部刪除重寫成此文，隨后的半個多月不斷反復(fù)改進(jìn),。 1. 引言本KMP原文最初寫于2年多前的2011年12月,，因當(dāng)時(shí)初次接觸KMP，思路混亂導(dǎo)致寫也寫得混亂,，如此,，留言也是“罵聲”一片。所以一直想找機(jī)會重新寫下KMP,，但苦于一直以來對KMP的理解始終不夠,，故才遲遲沒有修改本文。 然近期因在北京開了個算法班,，專門講解數(shù)據(jù)結(jié)構(gòu),、面試、算法,，才再次仔細(xì)回顧了這個KMP,，在綜合了一些網(wǎng)友的理解、以及跟我一起講算法的兩位講師朋友曹博,、鄒博的理解之后,，寫了9張PPT，發(fā)在微博上,。隨后,，一不做二不休，索性將PPT上的內(nèi)容整理到了本文之中（后來文章越寫越完整,，所含內(nèi)容早已不再是九張PPT 那樣簡單了）,。 KMP本身不復(fù)雜，但網(wǎng)上絕大部分的文章（包括本文的2011年版本）把它講混亂了,。下面,，咱們從暴力匹配算法講起，隨后闡述KMP的流程 步驟,、next 數(shù)組的簡單求解 遞推原理 代碼求解,，接著基于next 數(shù)組匹配，談到有限狀態(tài)自動機(jī),，next 數(shù)組的優(yōu)化,，KMP的時(shí)間復(fù)雜度分析,，最后簡要介紹兩個KMP的擴(kuò)展算法。 全文力圖給你一個最為完整最為清晰的KMP,，希望更多的人不再被KMP折磨或糾纏,，不再被一些混亂的文章所混亂，有何疑問,，歡迎隨時(shí)留言評論,，thanks。 2. 暴力匹配算法假設(shè)現(xiàn)在我們面臨這樣一個問題：有一個文本串S,，和一個模式串P,，現(xiàn)在要查找P在S中的位置，怎么查找呢,？ 如果用暴力匹配的思路,，并假設(shè)現(xiàn)在文本串S匹配到 i 位置，模式串P匹配到 j 位置,，則有：
理清楚了暴力匹配算法的流程及內(nèi)在的邏輯，咱們可以寫出暴力匹配的代碼,，如下：
舉個例子,，如果給定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”,，現(xiàn)在要拿模式串P去跟文本串S匹配,，整個過程如下所示： 1. S[0]為B，P[0]為A，不匹配,，執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]）,，令i = i - (j - 1)，j = 0”,，S[1]跟P[0]匹配,，相當(dāng)于模式串要往右移動一位（i=1，j=0） 2. S[1]跟P[0]還是不匹配,，繼續(xù)執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]）,，令i = i - (j - 1)，j = 0”,，S[2]跟P[0]匹配（i=2，j=0）,，從而模式串不斷的向右移動一位（不斷的執(zhí)行“令i = i - (j - 1),，j = 0”，i從2變到4,，j一直為0） 3. 直到S[4]跟P[0]匹配成功（i=4,，j=0），此時(shí)按照上面的暴力匹配算法的思路,，轉(zhuǎn)而執(zhí)行第①條指令：“如果當(dāng)前字符匹配成功（即S[i] == P[j]）,，則i++，j++”,，可得S[i]為S[5],，P[j]為P[1]，即接下來S[5]跟P[1]匹配（i=5,，j=1） 4. S[5]跟P[1]匹配成功,，繼續(xù)執(zhí)行第①條指令：“如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++,，j++”,，得到S[6]跟P[2]匹配（i=6，j=2）,，如此進(jìn)行下去 5. 直到S[10]為空格字符,，P[6]為字符D（i=10，j=6）,，因?yàn)椴黄ヅ?，重新?zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1),，j = 0”,，相當(dāng)于S[5]跟P[0]匹配（i=5，j=0） 6. 至此，我們可以看到,，如果按照暴力匹配算法的思路,，盡管之前文本串和模式串已經(jīng)分別匹配到了S[9]、P[5],，但因?yàn)镾[10]跟P[6]不匹配,，所以文本串回溯到S[5]，模式串回溯到P[0],，從而讓S[5]跟P[0]匹配,。 而S[5]肯定跟P[0]失配。為什么呢,？因?yàn)樵谥暗?步匹配中,，我們已經(jīng)得知S[5] = P[1] = B，而P[0] = A,，即P[1] != P[0],，故S[5]必定不等于P[0]，所以回溯過去必然會導(dǎo)致失配,。那有沒有一種算法,，讓i 不往回退，只需要移動j 即可呢,？ 答案是肯定的,。這種算法就是本文的主旨KMP算法，它利用之前已經(jīng)部分匹配這個有效信息,，保持i 不回溯,，通過修改j 的位置，讓模式串盡量地移動到有效的位置,。 3. KMP算法3.1 定義 Knuth-Morris-Pratt 字符串查找算法,，簡稱為 “KMP算法”，常用于在一個文本串S內(nèi)查找一個模式串P 的出現(xiàn)位置,，這個算法由Donald Knuth,、Vaughan Pratt、James H. Morris三人于1977年聯(lián)合發(fā)表,，故取這3人的姓氏命名此算法,。 下面先直接給出KMP的算法流程（如果感到一點(diǎn)點(diǎn)不適，沒關(guān)系,，堅(jiān)持下,，稍后會有具體步驟及解釋，越往后看越會柳暗花明?）：
此也意味著在某個字符失配時(shí)，該字符對應(yīng)的next 值會告訴你下一步匹配中,，模式串應(yīng)該跳到哪個位置（跳到next [j] 的位置）,。如果next [j] 等于0或-1，則跳到模式串的開頭字符,，若next [j] = k 且 k > 0,，代表下次匹配跳到j(luò) 之前的某個字符，而不是跳到開頭,，且具體跳過了k 個字符,。 轉(zhuǎn)換成代碼表示，則是：
繼續(xù)拿之前的例子來說,，當(dāng)S[10]跟P[6]匹配失敗時(shí)，KMP不是跟暴力匹配那樣簡單的把模式串右移一位，而是執(zhí)行第②條指令：“如果j != -1,，且當(dāng)前字符匹配失?。碨[i] != P[j]），則令 i 不變,，j = next[j]”,，即j 從6變到2（后面我們將求得P[6]，即字符D對應(yīng)的next 值為2）,，所以相當(dāng)于模式串向右移動的位數(shù)為j - next[j]（j - next[j] = 6-2 = 4）,。 向右移動4位后，S[10]跟P[2]繼續(xù)匹配,。為什么要向右移動4位呢,，因?yàn)橐苿?位后，模式串中又有個“AB”可以繼續(xù)跟S[8]S[9]對應(yīng)著,，從而不用讓i 回溯,。相當(dāng)于在除去字符D的模式串子串中尋找相同的前綴和后綴，然后根據(jù)前綴后綴求出next 數(shù)組,，最后基于next 數(shù)組進(jìn)行匹配（不關(guān)心next 數(shù)組是怎么求來的,，只想看匹配過程是咋樣的，可直接跳到下文3.3.4節(jié)）,。
綜上，KMP的next 數(shù)組相當(dāng)于告訴我們：當(dāng)模式串中的某個字符跟文本串中的某個字符匹配失配時(shí),，模式串下一步應(yīng)該跳到哪個位置,。如模式串中在j 處的字符跟文本串在i 處的字符匹配失配時(shí)，下一步用next [j] 處的字符繼續(xù)跟文本串i 處的字符匹配,，相當(dāng)于模式串向右移動 j - next[j] 位,。 接下來，分別具體解釋上述3個步驟,。 3.3 解釋3.3.1 尋找最長前綴后綴 如果給定的模式串是：“ABCDABD”，從左至右遍歷整個模式串,，其各個子串的前綴后綴分別如下表格所示：  也就是說,，原模式串子串對應(yīng)的各個前綴后綴的公共元素的最大長度表為（下簡稱《最大長度表》）： 因?yàn)槟Ｊ酱惺孜部赡軙兄貜?fù)的字符，故可得出下述結(jié)論：
下面,，咱們就結(jié)合之前的《最大長度表》和上述結(jié)論，進(jìn)行字符串的匹配,。如果給定文本串“BBC ABCDAB ABCDABCDABDE”,，和模式串“ABCDABD”，現(xiàn)在要拿模式串去跟文本串匹配,，如下圖所示：
通過上述匹配過程可以看出，問題的關(guān)鍵就是尋找模式串中最大長度的相同前綴和后綴,，找到了模式串中每個字符之前的前綴和后綴公共部分的最大長度后,，便可基于此匹配。而這個最大長度便正是next 數(shù)組要表達(dá)的含義,。 3.3.3 根據(jù)《最大長度表》求next 數(shù)組由上文,，我們已經(jīng)知道，字符串“ABCDABD”各個前綴后綴的最大公共元素長度分別為： 而且,，根據(jù)這個表可以得出下述結(jié)論
上文利用這個表和結(jié)論進(jìn)行匹配時(shí)，我們發(fā)現(xiàn),，當(dāng)匹配到一個字符失配時(shí),，其實(shí)沒必要考慮當(dāng)前失配的字符，更何況我們每次失配時(shí),，都是看的失配字符的上一位字符對應(yīng)的最大長度值,。如此,，便引出了next 數(shù)組。 給定字符串“ABCDABD”,，可求得它的next 數(shù)組如下： 把next 數(shù)組跟之前求得的最大長度表對比后,，不難發(fā)現(xiàn)，next 數(shù)組相當(dāng)于“最大長度值” 整體向右移動一位,，然后初始值賦為-1,。意識到了這一點(diǎn)，你會驚呼原來next 數(shù)組的求解竟然如此簡單：就是找最大對稱長度的前綴后綴,，然后整體右移一位,，初值賦為-1（當(dāng)然，你也可以直接計(jì)算某個字符對應(yīng)的next值,，就是看這個字符之前的字符串中有多大長度的相同前綴后綴）,。 換言之，對于給定的模式串：ABCDABD,，它的最大長度表及next 數(shù)組分別如下： 根據(jù)最大長度表求出了next 數(shù)組后,，從而有
而后,，你會發(fā)現(xiàn),，無論是基于《最大長度表》的匹配，還是基于next 數(shù)組的匹配,，兩者得出來的向右移動的位數(shù)是一樣的,。為什么呢？因?yàn)椋?/p>
所以，你可以把《最大長度表》看做是next 數(shù)組的雛形,，甚至就把它當(dāng)做next 數(shù)組也是可以的,，區(qū)別不過是怎么用的問題。 3.3.4 通過代碼遞推計(jì)算next 數(shù)組接下來,，咱們來寫代碼求下next 數(shù)組,。 基于之前的理解,，可知計(jì)算next 數(shù)組的方法可以采用遞推：
對于P的前j+1個序列字符：
一般的文章或教材可能就此一筆帶過,，但大部分的初學(xué)者可能還是不能很好的理解上述求解next 數(shù)組的原理，故接下來,，我再來著重說明下,。 如下圖所示,，假定給定模式串ABCDABCE，且已知next [j] = k（相當(dāng)于“p0 pk-1” = “pj-k pj-1” = AB,，可以看出k為2）,，現(xiàn)要求next [j + 1]等于多少？因?yàn)閜k = pj = C,，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）,。代表字符E前的模式串中，有長度k+1 的相同前綴后綴,。 但如果pk != pj 呢,？說明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。換言之,，當(dāng)pk != pj后,，字符E前有多大長度的相同前綴后綴呢？很明顯,，因?yàn)镃不同于D,，所以ABC 跟 ABD不相同，即字符E前的模式串沒有長度為k+1的相同前綴后綴,，也就不能再簡單的令：next[j + 1] = next[j] + 1 ,。所以，咱們只能去尋找長度更短一點(diǎn)的相同前綴后綴,。 結(jié)合上圖來講,，若能在前綴“ p0 pk-1 pk ” 中不斷的遞歸前綴索引k = next [k]，找到一個字符pk’ 也為D,，代表pk’ = pj,，且滿足p0 pk'-1 pk' = pj-k' pj-1 pj，則最大相同的前綴后綴長度為k' + 1,，從而next [j + 1] = k’ + 1 = next [k' ] + 1,。否則前綴中沒有D，則代表沒有相同的前綴后綴,，next [j + 1] = 0,。 那為何遞歸前綴索引k = next[k]，就能找到長度更小的相同前綴后綴呢,？這又歸根到next數(shù)組的含義,。為了尋找長度相同的前綴后綴，我們拿前綴 p0 pk-1 pk 去跟后綴pj-k pj-1 pj匹配,，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 繼續(xù)匹配,，如果p[ next[k] ]跟pj還是不匹配,，則下一步用p[ next[ next[k] ] ]去跟pj匹配,。相當(dāng)于在不斷的遞歸k = next[k]，直到要么找到長度更小的相同前綴后綴,，要么沒有長度更小的相同前綴后綴,。 所以，因最終在前綴ABC中沒有找到D,，故E的next 值為0： 模式串的后綴：ABDE 模式串的前綴：ABC 前綴右移兩位： ABC 給定模式串DABCDABDE,，我們很順利的求得字符D之前的“DABCDAB”的各個子串的最長相同前綴后綴的長度分別為0 0 0 0 1 2 3,，但當(dāng)遍歷到字符D，要求包括D在內(nèi)的“DABCDABD”最長相同前綴后綴時(shí),，我們發(fā)現(xiàn)pj處的字符D跟pk處的字符C不一樣,，換言之，前綴DABC的最后一個字符C 跟后綴DABD的最后一個字符D不相同,，所以不存在長度為4的相同前綴后綴,。 怎么辦呢？既然沒有長度為4的相同前綴后綴,，咱們可以尋找長度短點(diǎn)的相同前綴后綴,，最終，因在p0處發(fā)現(xiàn)也有個字符D,，p0 = pj,，所以p[j]對應(yīng)的長度值為1，相當(dāng)于E對應(yīng)的next 值為1,。 綜上,，可以通過遞推求得next 數(shù)組，代碼如下所示：
用代碼重新計(jì)算下“ABCDABD”的next 數(shù)組,，以驗(yàn)證之前通過“最長相同前綴后綴長度值右移一位，然后初值賦為-1”得到的next 數(shù)組是否正確,，計(jì)算結(jié)果如下表格所示： 從上述表格可以看出,，無論是之前通過“最長相同前綴后綴長度值右移一位，然后初值賦為-1”得到的next 數(shù)組,，還是之后通過代碼遞推計(jì)算求得的next 數(shù)組,，結(jié)果是完全一致的。 3.3.5 基于《next 數(shù)組》匹配下面，我們來基于next 數(shù)組進(jìn)行匹配,。 還是給定文本串“BBC ABCDAB ABCDABCDABDE”,，和模式串“ABCDABD”，現(xiàn)在要拿模式串去跟文本串匹配,，如下圖所示： 在正式匹配之前,，讓我們來再次回顧下上文2.1節(jié)所述的KMP算法的匹配流程：
匹配過程一模一樣,。也從側(cè)面佐證了,，next 數(shù)組確實(shí)是只要將各個最大前綴后綴的公共元素的長度值右移一位，且把初值賦為-1 即可,。 3.3.6 基于《最大長度表》與基于《next 數(shù)組》等價(jià)我們已經(jīng)知道,，利用next 數(shù)組進(jìn)行匹配失配時(shí)，模式串向右移動 j - next [ j ] 位,，等價(jià)于已匹配字符數(shù) - 失配字符的上一位字符所對應(yīng)的最大長度值,。原因是：
但為何本文不直接利用next 數(shù)組進(jìn)行匹配呢,？因?yàn)閚ext 數(shù)組不好求，而一個字符串的前綴后綴的公共元素的最大長度值很容易求,。例如若給定模式串“ababa”,，要你快速口算出其next 數(shù)組，乍一看,，每次求對應(yīng)字符的next值時(shí),，還得把該字符排除之外，然后看該字符之前的字符串中有最大長度為多大的相同前綴后綴,，此過程不夠直接,。而如果讓你求其前綴后綴公共元素的最大長度，則很容易直接得出結(jié)果：0 0 1 2 3,，如下表格所示： 然后這5個數(shù)字 全部整體右移一位,，且初值賦為-1，即得到其next 數(shù)組：-1 0 0 1 2,。 3.3.7 Next 數(shù)組與有限狀態(tài)自動機(jī) next 負(fù)責(zé)把模式串向前移動,，且當(dāng)?shù)趈位不匹配的時(shí)候，用第next[j]位和主串匹配,，就像打了張“表”,。此外，next 也可以看作有限狀態(tài)自動機(jī)的狀態(tài),，在已經(jīng)讀了多少字符的情況下,，失配后，前面讀的若干個字符是有用的,。
3.3.8 Next 數(shù)組的優(yōu)化行文至此,，咱們?nèi)媪私饬吮┝ζヅ涞乃悸贰MP算法的原理,、流程,、流程之間的內(nèi)在邏輯聯(lián)系，以及next 數(shù)組的簡單求解（《最大長度表》整體右移一位,，然后初值賦為-1）和代碼求解,，最后基于《next 數(shù)組》的匹配，看似洋洋灑灑,，清晰透徹,，但以上忽略了一個小問題,。 比如，如果用之前的next 數(shù)組方法求模式串“abab”的next 數(shù)組,，可得其next 數(shù)組為-1 0 0 1（0 0 1 2整體右移一位,，初值賦為-1），當(dāng)它跟下圖中的文本串去匹配的時(shí)候,，發(fā)現(xiàn)b跟c失配,，于是模式串右移j - next[j] = 3 - 1 =2位。 右移2位后,，b又跟c失配,。事實(shí)上，因?yàn)樵谏弦徊降钠ヅ渲?，已?jīng)得知p[3] = b，與s[3] = c失配,，而右移兩位之后,，讓p[ next[3] ] = p[1] = b 再跟s[3]匹配時(shí)，必然失配,。問題出在哪呢,？ 問題出在不該出現(xiàn)p[j] = p[ next[j] ]。為什么呢,？理由是：當(dāng)p[j] != s[i] 時(shí),，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ],，必然導(dǎo)致后一步匹配失?。ㄒ?yàn)閜[j]已經(jīng)跟s[i]失配，然后你還用跟p[j]等同的值p[next[j]]去跟s[i]匹配,，很顯然,，必然失配），所以不能允許p[j] = p[ next[j ]],。如果出現(xiàn)了p[j] = p[ next[j] ]咋辦呢,？如果出現(xiàn)了，則需要再次遞歸,，即令next[j] = next[ next[j] ],。 所以，咱們得修改下求next 數(shù)組的代碼,。
利用優(yōu)化過后的next 數(shù)組求法,，可知模式串“abab”的新next數(shù)組為：-1 0 -1 0?？赡苡行┳x者會問：原始next 數(shù)組是前綴后綴最長公共元素長度值右移一位,， 然后初值賦為-1而得，那么優(yōu)化后的next 數(shù)組如何快速心算出呢,？實(shí)際上,，只要求出了原始next 數(shù)組，便可以根據(jù)原始next 數(shù)組快速求出優(yōu)化后的next 數(shù)組,。還是以abab為例,，如下表格所示： 只要出現(xiàn)了p[next[j]] = p[j]的情況，則把next[j]的值再次遞歸,。例如在求模式串“abab”的第2個a的next值時(shí),，如果是未優(yōu)化的next值的話，第2個a對應(yīng)的next值為0,，相當(dāng)于第2個a失配時(shí),，下一步匹配模式串會用p[0]處的a再次跟文本串匹配，必然失配,。所以求第2個a的next值時(shí),，需要再次遞歸：next[2] = next[ next[2] ] = next[0] = -1（此后，根據(jù)優(yōu)化后的新next值可知,，第2個a失配時(shí),，執(zhí)行“如果j = -1，或者當(dāng)前字符匹配成功（即S[i] == P[j]）,，都令i++,，j++，繼續(xù)匹配下一個字符”）,，同理,，第2個b對應(yīng)的next值為0。 對于優(yōu)化后的next數(shù)組可以發(fā)現(xiàn)一點(diǎn)：如果模式串的后綴跟前綴相同,，那么它們的next值也是相同的,，例如模式串abcabc，它的前綴后綴都是abc,，其優(yōu)化后的next數(shù)組為：-1 0 0 -1 0 0,，前綴后綴abc的next值都為-1 0 0。 然后引用下之前3.1節(jié)的KMP代碼：
接下來,，咱們繼續(xù)拿之前的例子說明,，整個匹配過程如下： 1. S[3]與P[3]匹配失敗。 2. S[3]保持不變,，P的下一個匹配位置是P[next[3]],，而next[3]=0,，所以P[next[3]]=P[0]與S[3]匹配。 3. 由于上一步驟中P[0]與S[3]還是不匹配,。此時(shí)i=3,，j=next [0]=-1,，由于滿足條件j==-1,，所以執(zhí)行“++i, ++j”,，即主串指針下移一個位置，P[0]與S[4]開始匹配,。最后j==pLen,，跳出循環(huán)，輸出結(jié)果i - j = 4（即模式串第一次在文本串中出現(xiàn)的位置）,，匹配成功，算法結(jié)束,。 3.4 KMP的時(shí)間復(fù)雜度分析 相信大部分讀者讀完上文之后,，已經(jīng)發(fā)覺其實(shí)理解KMP非常容易，無非是循序漸進(jìn)把握好下面幾點(diǎn)：
如之前的圖所示： 接下來,，咱們來分析下KMP的時(shí)間復(fù)雜度。分析之前,，先來回顧下KMP匹配算法的流程： “KMP的算法流程：
我們發(fā)現(xiàn)如果某個字符匹配成功，模式串首字符的位置保持不動,，僅僅是i++,、j++；如果匹配失配,，i 不變（即 i 不回溯）,，模式串會跳過匹配過的next [j]個字符。整個算法最壞的情況是,，當(dāng)模式串首字符位于i - j的位置時(shí)才匹配成功,，算法結(jié)束。 4. 擴(kuò)展1：BM算法KMP的匹配是從模式串的開頭開始匹配的，而1977年,，德克薩斯大學(xué)的Robert S. Boyer教授和J Strother Moore教授發(fā)明了一種新的字符串匹配算法：Boyer-Moore算法,，簡稱BM算法。該算法從模式串的尾部開始匹配,，且擁有在最壞情況下O(N)的時(shí)間復(fù)雜度,。在實(shí)踐中，比KMP算法的實(shí)際效能高,。 BM算法定義了兩個規(guī)則：
下面舉例說明BM算法,。例如,，給定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”,，現(xiàn)要查找模式串是否在文本串中，如果存在,，返回模式串在文本串中的位置,。 1. 首先，"文本串"與"模式串"頭部對齊,，從尾部開始比較,。"S"與"E"不匹配。這時(shí),，"S"就被稱為"壞字符"（bad character）,，即不匹配的字符，它對應(yīng)著模式串的第6位,。且"S"不包含在模式串"EXAMPLE"之中（相當(dāng)于最右出現(xiàn)位置是-1）,，這意味著可以把模式串后移6-(-1)=7位，從而直接移到"S"的后一位,。 2. 依然從尾部開始比較,，發(fā)現(xiàn)"P"與"E"不匹配,，所以"P"是"壞字符"。但是,，"P"包含在模式串"EXAMPLE"之中,。因?yàn)椤癙”這個“壞字符”對應(yīng)著模式串的第6位（從0開始編號），且在模式串中的最右出現(xiàn)位置為4,，所以,，將模式串后移6-4=2位，兩個"P"對齊,。 3. 依次比較,，得到 “MPLE”匹配，稱為"好后綴"（good suffix）,，即所有尾部匹配的字符串,。注意，"MPLE",、"PLE",、"LE"、"E"都是好后綴,。 4. 發(fā)現(xiàn)“I”與“A”不匹配：“I”是壞字符,。如果是根據(jù)壞字符規(guī)則，此時(shí)模式串應(yīng)該后移2-(-1)=3位,。問題是,，有沒有更優(yōu)的移法？ 5. 更優(yōu)的移法是利用好后綴規(guī)則：當(dāng)字符失配時(shí),，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現(xiàn)的位置,，且如果好后綴在模式串中沒有再次出現(xiàn)，則為-1,。 所有的“好后綴”（MPLE,、PLE、LE,、E）之中,，只有“E”在“EXAMPLE”的頭部出現(xiàn)，所以后移6-0=6位,。 可以看出,，“壞字符規(guī)則”只能移3位，“好后綴規(guī)則”可以移6位,。每次后移這兩個規(guī)則之中的較大值,。這兩個規(guī)則的移動位數(shù)，只與模式串有關(guān)，與原文本串無關(guān),。 6. 繼續(xù)從尾部開始比較,，“P”與“E”不匹配，因此“P”是“壞字符”,，根據(jù)“壞字符規(guī)則”,，后移 6 - 4 = 2位。因?yàn)槭亲詈笠晃痪褪?，尚未獲得好后綴,。 由上可知，BM算法不僅效率高,，而且構(gòu)思巧妙,，容易理解。 5. 擴(kuò)展2：Sunday算法上文中,，我們已經(jīng)介紹了KMP算法和BM算法,，這兩個算法在最壞情況下均具有線性的查找時(shí)間。但實(shí)際上,，KMP算法并不比最簡單的c庫函數(shù)strstr()快多少,，而BM算法雖然通常比KMP算法快，但BM算法也還不是現(xiàn)有字符串查找算法中最快的算法,，本文最后再介紹一種比BM算法更快的查找算法即Sunday算法,。 Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：
下面舉個例子說明下Sunday算法,。假定現(xiàn)在要在文本串"substring searching algorithm"中查找模式串"search",。 1. 剛開始時(shí)，把模式串與文本串左邊對齊： substring searching algorithm 4. 匹配成功,。 回顧整個過程，我們只移動了兩次模式串就找到了匹配位置,，緣于Sunday算法每一步的移動量都比較大,，效率很高。完,。 6. 參考文獻(xiàn)
7. 后記對之前混亂的文章給廣大讀者帶來的困擾表示致歉，對重新寫就后的本文即將給讀者帶來的清晰表示欣慰,。希望大部分的初學(xué)者,，甚至少部分的非計(jì)算機(jī)專業(yè)讀者也能看懂此文。有任何問題,，歡迎隨時(shí)批評指正,，thanks。 July,、二零一四年八月二十二日晚九點(diǎn),。 |
|
|
