KMP 字符串模式匹配详解

1、KMP 字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。一 . 简单匹配算法 基本的模式匹配算法：以主串的某个字符与子串的第一个字符相比较，若相等，则继续比较二者的后一个字符，否则主串的字符指针从开始与子串第一个字符比较处后移一个位置，而子串的字符指针重新指向子串的第一个字符。例如：在串S=”abcabcabdabba”中查找T=” abcabd”:先是比较S1和T1是否相等，然后比较S2 和T2是否相等我们发现一直比较到S6 和T6才不等。如图：

2、0;当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标4。如图：二 . KMP 匹配算法 KMP算法：KMP算法是对传统模式匹配算法的较大改进，在传统的模式匹配算法中，当出现主串中的字符与子串中的字符不等时，同时向前回溯了两个指针，一个是主串的指针，一个是子串的指针。而KMP算法的基本思路是在不回溯主串的指针，而只回溯子串的指针的情

3、况下完成模式匹配，这样就省去了回溯主串指针进行比较的一部分时间。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S6 和T6不等后，S下标不是回溯到2，T下标也不是回溯到开始，而是根据T中T6=d的模式函数值（next6=3，为什么？后面讲），直接比较S6 和T3是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。最终在S中找到了T。如图：next6=3含义： 其实这个3表示T6=d的前面有2个字符和开始的两个字符相同”。请看图&

4、#160;：因为，S5 =T5，S4 =T4，根据next6=3，有T4=T1，T5 =T2，所以S4=T1，S5 =T2（两对相当于间接比较过了），因此，接下来比较S6 和T3是否相等。有人可能会问：S4和T1，S5 和T2是根据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  意义：任何串的第一个字符的模式值规定为0。（2）nextj=k  意义：模式串T中下标为j的字符，

6、如果j的前面k1个字符与开头的k1个字符相等， 即:     T1T2。Tk-1 = Tj-k+1Tj-k+2Tj-1（3）nextj=1   其他情况。例1）求T=“abcac”的模式函数的值。下标12345Tabcacnext01112例2） 求T=”ababcaabc” 的模式函数的值。下标123456789Tababcaabcnext011231223例3)  求 T=”abCabCad” 的模式函数的值。下标12345678TabCabCadnext01112345课后题：求 T=” ababc

7、abababc” 的模式函数的值。四 . nextn 不足与改进：KMP的改进算法：KMP的改进算法主要是针对求NEXT数组的算法思想进行的改进。为了提高NEXT数组的效率，引入了NEXTVAL数组(即NEXT的改进值)。NEXTVAL避免了当出现匹配不成功时再接着进行重复比较的情况。比如：“abcdabce”模式串中，NEXT值为(0 1 1 1 1 2 3 4)，NEXTVAL值为(0 1 1 1 0 1 1 4)。当比较到T7=C不成功时，原NEXT的值跟T3比较，可事实上，T3也是C，与T7相同，所以可以直接跟T1比较。举例 ：若T=“abcab”的模式函数的值 下标12345Tabc

8、abnext01112若S“abcadcabcab”，nextn 改进为nextvaln：如果Tj!=Tk，k=nextj否则k=nextk下标12345Tabcabnext01100练习：求T=”AAAAAAAAAAB” 的模式函数值，并用后面的求模式函数值函数验证。五 . nextn 意义 ：设在字符串S中查找模式串T，若Sm!=Tn,那么，取Tn的模式函数值nextn,1. nextn= 0 表示Sm和T1间接比较过了，不相等，下一次比较 Sm+1 和T12. nextn=1   表示比较过程中产生了不相等，下一次比较 Sm 和T1。3. next

9、n= k   表示Sm的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较Sm和Tk相等吗？4. 其他值，不可能。课后习题：1. 设有串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、试计算执行concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)操作的结果。3. 求串ababaaababaa 的next函数值。4. 模式串t=abcaabbcaabdab，求模式串的next和nextval函数的值。5. 给出字符串abacabaaad在KMP算法中的next和nextval数组。6. 对S=aabcbabcaabcaaba，T=bca，画出以T为模式串，S为目标串的匹配过程。7. 若S=software,则其子串的数目是多少？习题答案：5. 设有串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，试计算执行concat(replace(S1,subst

12、r(S1,length(S2),length(S3),S3),substr(S4,index(S2,8),length(S2)操作的结果。 【解答】 结果为: ABC#G12347. 求串ababaaababaa 的next函数值。【解答】 j123456789101112 串ababaaababaanextj0112342234568. 模式串t=abcaabbcaabdab，求模式串的next和nextval函数的值。【解答】 j1234567891011121314 串abcaabbcaabdabnxtj01112231122312nxtvalj011021310213015.给出字符串abacabaaad在KMP算法中的next和nextval数组。【解答】 j12345678910 串abacabaaadnxtj0112123422nx