KMP 字符串模式匹配詳解

1、KMP 字符串模式匹配詳解KMP字符串模式匹配通俗點說就是一種在一個字符串中定位另一個串的高效算法。簡單匹配算法的時間復(fù)雜度為O(m*n);KMP匹配算法?？梢宰C明它的時間復(fù)雜度為O(m+n).。一 . 簡單匹配算法 基本的模式匹配算法：以主串的某個字符與子串的第一個字符相比較，若相等，則繼續(xù)比較二者的后一個字符，否則主串的字符指針從開始與子串第一個字符比較處后移一個位置，而子串的字符指針重新指向子串的第一個字符。例如：在串S=”abcabcabdabba”中查找T=” abcabd”:先是比較S1和T1是否相等，然后比較S2 和T2是否相等我們發(fā)現(xiàn)一直比較到S6 和T6才不等。如圖：

2、0;當(dāng)這樣一個失配發(fā)生時，T下標(biāo)必須回溯到開始，S下標(biāo)回溯的長度與T相同，然后S下標(biāo)增1,然后再次比較。如圖：這次立刻發(fā)生了失配，T下標(biāo)又回溯到開始，S下標(biāo)增1,然后再次比較。如圖：又一次發(fā)生了失配，所以T下標(biāo)又回溯到開始，S下標(biāo)增1,然后再次比較。這次T中的所有字符都和S中相應(yīng)的字符匹配了。函數(shù)返回T在S中的起始下標(biāo)4。如圖：二 . KMP 匹配算法 KMP算法：KMP算法是對傳統(tǒng)模式匹配算法的較大改進，在傳統(tǒng)的模式匹配算法中，當(dāng)出現(xiàn)主串中的字符與子串中的字符不等時，同時向前回溯了兩個指針，一個是主串的指針，一個是子串的指針。而KMP算法的基本思路是在不回溯主串的指針，而只回溯子串的指針的情

3、況下完成模式匹配，這樣就省去了回溯主串指針進行比較的一部分時間。KMP算法的核心思想是利用已經(jīng)得到的部分匹配信息來進行后面的匹配過程。還是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，當(dāng)?shù)谝淮嗡阉鞯絊6 和T6不等后，S下標(biāo)不是回溯到2，T下標(biāo)也不是回溯到開始，而是根據(jù)T中T6=d的模式函數(shù)值（next6=3，為什么？后面講），直接比較S6 和T3是否相等，因為相等，S和T的下標(biāo)同時增加;因為又相等，S和T的下標(biāo)又同時增加。最終在S中找到了T。如圖：next6=3含義： 其實這個3表示T6=d的前面有2個字符和開始的兩個字符相同”。請看圖&

4、#160;：因為，S5 =T5，S4 =T4，根據(jù)next6=3，有T4=T1，T5 =T2，所以S4=T1，S5 =T2（兩對相當(dāng)于間接比較過了），因此，接下來比較S6 和T3是否相等。有人可能會問：S4和T1，S5 和T2是根據(jù)next6=3間接比較相等，那S2和T1，S3 和T1之間又是怎么跳過，可以不比較呢？因為S1=T1，S2=T2，S3=T3，而T1 != T2, T2 != T3,=> S1 != S2,S2 != S3,所以S2 != T1,S3 != T1. 還是從理論上間接比較了。三 .

5、怎么求串的模式值 nextn 定義 ：          0   如果j=1nextj= Maxk|1<k<j且'p1.pk-1'='pj-k+1.pj-1'          1   其它情況（1）next1=0  意義：任何串的第一個字符的模式值規(guī)定為0。（2）nextj=k  意義：模式串T中下標(biāo)為j的字符，

6、如果j的前面k1個字符與開頭的k1個字符相等， 即:     T1T2。Tk-1 = Tj-k+1Tj-k+2Tj-1（3）nextj=1   其他情況。例1）求T=“abcac”的模式函數(shù)的值。下標(biāo)12345Tabcacnext01112例2） 求T=”ababcaabc” 的模式函數(shù)的值。下標(biāo)123456789Tababcaabcnext011231223例3)  求 T=”abCabCad” 的模式函數(shù)的值。下標(biāo)12345678TabCabCadnext01112345課后題：求 T=” ababc

7、abababc” 的模式函數(shù)的值。四 . nextn 不足與改進：KMP的改進算法：KMP的改進算法主要是針對求NEXT數(shù)組的算法思想進行的改進。為了提高NEXT數(shù)組的效率，引入了NEXTVAL數(shù)組(即NEXT的改進值)。NEXTVAL避免了當(dāng)出現(xiàn)匹配不成功時再接著進行重復(fù)比較的情況。比如：“abcdabce”模式串中，NEXT值為(0 1 1 1 1 2 3 4)，NEXTVAL值為(0 1 1 1 0 1 1 4)。當(dāng)比較到T7=C不成功時，原NEXT的值跟T3比較，可事實上，T3也是C，與T7相同，所以可以直接跟T1比較。舉例 ：若T=“abcab”的模式函數(shù)的值 下標(biāo)12345Tabc

8、abnext01112若S“abcadcabcab”，nextn 改進為nextvaln：如果Tj!=Tk，k=nextj否則k=nextk下標(biāo)12345Tabcabnext01100練習(xí)：求T=”AAAAAAAAAAB” 的模式函數(shù)值，并用后面的求模式函數(shù)值函數(shù)驗證。五 . nextn 意義 ：設(shè)在字符串S中查找模式串T，若Sm!=Tn,那么，取Tn的模式函數(shù)值nextn,1. nextn= 0 表示Sm和T1間接比較過了，不相等，下一次比較 Sm+1 和T12. nextn=1   表示比較過程中產(chǎn)生了不相等，下一次比較 Sm 和T1。3. next

9、n= k   表示Sm的前k個字符與T中的開始k個字符已經(jīng)間接比較相等了，下一次比較Sm和Tk相等嗎？4. 其他值，不可能。課后習(xí)題：1. 設(shè)有串S=good，T=Iamastudent，R=！，求： （1）StringConcat(T,R) （2）SubString(T,8,7） （3）StringLength(T) （4）Index(T, a) （5）StringInsert(T,S,8) （6）replace(T, SubString(T,8,7), teacher) 2. 若串S1=ABCDEFG， S2=9898，S3=#，S4=012345，

10、試計算執(zhí)行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)操作的結(jié)果。3. 求串a(chǎn)babaaababaa 的next函數(shù)值。4. 模式串t=abcaabbcaabdab，求模式串的next和nextval函數(shù)的值。5. 給出字符串a(chǎn)bacabaaad在KMP算法中的next和nextval數(shù)組。6. 對S=aabcbabcaabcaaba，T=bca，畫出以T為模式串，S為目標(biāo)串的匹配過程。7. 若S=software,則其子串的數(shù)目是多少？習(xí)題答案：5. 設(shè)有串S=go

11、od，T=Iamastudent，R=！，求： （1）StringConcat(T,R) =I am a student! （2）SubString(T,8,7） =student （3）StringLength(T) =14 （4）Index(T, a) =3 （5）StringInsert(T,S,8) =I am a goodstudent! （6）replace(T, SubString(T,8,7), teacher) =I am a teacher6. 若串S1=ABCDEFG， S2=9898，S3=#，S4=012345，試計算執(zhí)行concat(replace(S1,subst

12、r(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)操作的結(jié)果。 【解答】 結(jié)果為: ABC#G12347. 求串a(chǎn)babaaababaa 的next函數(shù)值?！窘獯稹?j123456789101112 串a(chǎn)babaaababaanextj0112342234568. 模式串t=abcaabbcaabdab，求模式串的next和nextval函數(shù)的值?！窘獯稹?j1234567891011121314 串a(chǎn)bcaabbcaabdabnxtj01112231122312nxtvalj011021310213015.給出字符串a(chǎn)bacabaaad在KMP算法中的next和nextval數(shù)組?！窘獯稹?j12345678910 串a(chǎn)bacabaaadnxtj0112123422nx