数据结构与算法—串的模式匹配

《数据结构与算法—串的模式匹配》由会员分享，可在线阅读，更多相关《数据结构与算法—串的模式匹配（5页珍藏版）》请在装配图网上搜索。

1、KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高 效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时 间复杂度为O(m+n).。一. 简单匹配算法先来看一个简单匹配算法的函数：int Index_BF ( char S , char T , int pos )/*若串S中从第pos(S的下标0Wpos个字符起存在和串T相同的子串，则称匹配成功，返回第一个这样的子串在串S中的下标，否则返回-1*/int i 二 pos, j = 0;while ( Si+j != 0 & Tj != 0)if ( Si+j = Tj)j +;

2、 /继续比较后一字符elsei +; j = 0; /重新开始新的一轮匹配if ( Tj = 0)ret urn i; /匹配成功 返回下标elseret urn -1; /串S中(第pos个字符起)不存在和串T相同的子串 / Index_BF此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T 相比较。即从j=0起比较Si+j与Tj,若相等，则在主串S中存在以i为 起始位置匹配成功的可能性，继续往后比较(j逐步增1)，直至与T串中最后 一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的匹配 ，即将串T向后滑动一位，即i增1,而j退回至0，重新开始新一轮的匹配。例如

3、：在串 s二” abcabcabdabba” 中查找 T二” abcabd”(我们 可以假设从下标0开始):先是比较S0和T0是否相等，然后比较S1和T1 是否相等我们发现一直比较到S5和T5才不等。如图：0 1 2 3 4 5 6 7 8 9 10 11 12 13abcabcabdabbao 、?f、l/、 ./、zFbcaIbdo0 1 2 3 4 5 6当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T 相同，然后S下标增1,然后再次比较。如图：这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。 如图：0123456789 10 口 12 13S可朗心|列

4、bt |規Ibid函|b |b|才师abcbd0 12 3 4 5 6这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。 如图：0 1 2 3 4 5 6 7 8 9 10 11 12 13abcabcabdabbaoabcabd0 12 3 4 5 6又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。 这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标 3。如图:0 1 2 3 4 5 6 7 8 9 10 11 12 13a b c :a b :abdabbavobJii.f I、Fabcabdo0 1 2 3 4 5 6二. KMP匹

5、配算法还是相同的例子，在s二” abcabcabdabba” 中查找t二” abcabd” , 如果使用KMP匹配算法，当第一次搜索到S5和T5不等后，S下标不是回溯 到1, T下标也不是回溯到开始，而是根据T中T5=d的模式函数值(next5=2，为什么？后面讲)，直接比较S5和T2是否相等，因为相等, S和T的下标同时增加；因为又相等，S和T的下标又同时增加。最终在S 中找到了 T。如图：0 1 2 3 4 5 6 7 8 9 10 11 12 13S abcafocabdabba；o、 TaVJ-a b c abd0 12 3 4 5 6KMP匹配算法和简单匹配算法效率比较，一个极端的例

6、子是：在 S二 “AAAAAAAAB“(100个 A)中查找T二” AAAAAAAAAB”，简单匹配算法 每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标 也要回溯相同长度后增1,继续比较。如果使用KMP匹配算法，就不必回溯.对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O (m+n)， 因此在多数的实际应用场合下被应用。KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过 程。看前面的例子。为什么T5=d的模式函数值等于2(next5=2)，其 实这个2表示T5=d的前面有2个字符和开始的两个字符相同，且 T5=d不等于开始的两个字符之后的第三个字

7、符(T2 = c ) 如图：abcabd012345也就是说，如果开始的两个字符之后的第三个字符也为d，那么，尽管 T5=d的前面有2个字符和开始的两个字符相同，T5=d的模式函数 值也不为2,而是为0。前面我说：在 s=”abcabcabdabba” 中查找 t二” abcabd”，如 果使用KMP匹配算法，当第一次搜索到S5和T5不等后，S下标不是回溯到 1，T下标也不是回溯到开始，而是根据T中T5=d的模式函数值，直接比 较S5和T2是否相等。为什么可以这样？刚才我又说：“(next5=2)，其实这个2表示T5=d的前面有 2个字符和开始的两个字符相同”。请看图：因为，S4 =T4，S3

8、 =T3， 根据 nex t5=2,有 T3=T0，T4 =T1，所以 S3=T0，S4 =T1 (两对相当于间接比较过了)，因此，接下来比较S5和T2是否相等。abcabd012345有人可能会问：S3和T0，S4和T1是根据next5=2间接比较相 等，那S1和T0，S2和T0之间又是怎么跳过，可以不比较呢？因为 S0=T0，S1=T1，S2=T2，而 T0 != T1,T1 != T2,= S0 != S1,S1 != S2,所以 S1 != T0,S2 != T0.还是从理论上间接比较了。有人疑问又来了，你分析的是不是特殊轻况啊。假设S不变，在S中搜索T=“abaabd”呢？答：这种情

9、况，当比较到S2 和T2时，发现不等，就去看next2的值，next2=-1，意思是S2已经和 T0间接比较过了，不相等，接下来去比较S3和T0吧。假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S2 和T2 时,发现不等,就去看nex t 2的值，nex t2=0,意思是S2已经和T2 比较过了，不相等，接下来去比较S2和T0吧。假设s二” abaabcabdabba”在S中搜索T二“abaabd”呢？答：这种情况当比较到S5和T5时，发现不等，就去看next5的值，next5=2，意思 是前面的比较过了，其中，S5的前面有两个字符和T的开始两个相等，接下来 去比较S5和T

10、2吧。总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值nextn 呢？（本文中next值、模式函数值、模式值是一个意思。）三. 怎么求串的模式值nextn定义：（1）next0= -1意义：任何串的第一个字符的模式值规定为-1。（2）nextj= -1 意义：模式串T中下标为j的字符，如果与首字符相同，且j的前面的1k个字符与开头的1k 个字符不等（或者相等但Tk=Tj）（lWk）。女如 T二” abCabCad” 则 next6=-1,因 T3=T6（3） nextj二k意义：模式串T中下标为j的字符，如果j的前面k 个字符与开头的k个字符相等，且Tj != Tk （lWk）。即 T0T1T2。Tk-1=Tj-kTj-k+1Tj-k+2Tj-1 且 Tj != Tk. （lWk）;j=0 意义：除（1）（2）（3）的其他情况。举例：01）求丁=“3匕。3。”的模式函数的值。nex t 0= -1 根据（1）next 1=0 根据（4） 因（3）有 1=k 不能说，j=1,Tj-1=T0 next2=0 根据（4） 因（3）有 1=k （T0=a） != （T1=b） nex t 3= -1 根据（2）next4=1 根据（3） T0=T3且 T1=T4下标01234Tabcacnex t-100-11