第4章串第2讲-串的模式匹配

1、成功成功是指在目标串是指在目标串s中找到一个模式中找到一个模式串串t t是是s的子的子串，返回串，返回t在在s中的位置。中的位置。不不成功成功则指目标串则指目标串s中不存在模式中不存在模式串串t t不是不是s的子的子串，返回串，返回- -1。 目标串目标串s模式串模式串t是是子子串串吗？吗？模式匹配模式匹配1/29 Brute-Force简称为简称为BF算法算法，亦称简单匹配，亦称简单匹配算法。采用穷算法。采用穷举的思路。举的思路。4.4.1 Brute-Force算法算法 a a a a b c d a b c a b c 匹配成功匹配成功s:t: a b c a b c 算法的思路是从s的

2、每一个字符开始依次与t的字符进行匹配。2/29 例如例如，设目标串，设目标串s=“aaaaab”，模式串，模式串t=“aaab”。s的长度为的长度为n（n=6），），t的长度为的长度为m（m=4）。BF算法算法的匹配过程的匹配过程如下。如下。a a a a a ba a a bs：t：ij匹配失败：匹配失败：i=i- -j+1=1 （回退）（回退） j=0 （从头开始）（从头开始）3/29a a a a a ba a a bs：t：ij匹配失败：匹配失败：i=i- -j+1=2（回退）（回退）j=0（从头开始）（从头开始）i=1，j=04/29a a a a a ba a a bs：t：ij匹

3、配成功：匹配成功：i=6，j=4返回返回i- -t.length=2i=2，j=05/29int index(SqString s,SqString t) int i=0, j=0; while (is.length & j=t.length)return(i-t.length);/返回匹配的第一个字符的下标返回匹配的第一个字符的下标 elsereturn(-1);/模式匹配不成功模式匹配不成功对应的对应的BF算法如下算法如下：6/29算法算法在字符在字符比较不相等比较不相等，需要回溯，需要回溯（即（即i=i- -j+1）：即退）：即退到到s中的下一个字符开始进行继续匹配。中的下一个字

4、符开始进行继续匹配。最好最好情况下的时间复杂度为情况下的时间复杂度为O(m)。最坏最坏情况下的时间复杂度为情况下的时间复杂度为O(nm)。 平均平均的时间复杂度为的时间复杂度为O(nm)。BF算法分析：算法分析：7/29 4.3.2 KMP算法算法 KMP算法是算法是D.E.Knuth、J.H.Morris和和V.R.Pratt共同提共同提出的，简称出的，简称KMP算法算法。 该该算法较算法较BF算法有较大改进，主要是算法有较大改进，主要是消除了主串指针消除了主串指针的回溯的回溯，从而使算法效率有了某种程度的提高。，从而使算法效率有了某种程度的提高。8/29a a a a a b0 1 2 3

5、 4 5a a a b从从t中发现：中发现：b前面有前面有2个字符和开头的个字符和开头的2个字符相同个字符相同s:t:开始匹配的字符开始匹配的字符下次开始匹配的字符下次开始匹配的字符用一用一个数组个数组next保存：保存：next3=2下次匹配的字符：下次匹配的字符：s3和和tnext3即即t2目标串目标串s=“aaaaab”，模式串模式串t=“aaab”。 KMP算法用算法用next数组保存部分匹配信息数组保存部分匹配信息的演示的演示9/29 模式模式串串t存在某个存在某个k（0kj），），使得以下成立使得以下成立: “t0t1tk -1” = “ tj-ktj-k+1tj-1 ”开头的开头

6、的k个字符个字符tj前面的前面的k个字符个字符nextj是是指指tj字符字符前有前有多少多少个字符与个字符与t开头的字符相同。开头的字符相同。 例如，例如，t= “a b a b c” 考虑考虑t4=c 0 1 2 3 4 有有t0t1 t2t3 = ab k=2 所以所以next4 = k = 2。10/29j0123tjaaabnextj MAX k | 0kj，且，且“t0t1tk-1” = “tj-ktj-k+1tj-1” 当此集合非空时当此集合非空时 - -1 当当j=0时时 0 其他其他情况情况nextj=t=“aaab”对应对应的的next数组如下数组如下:归纳起来，定义归纳起来

7、，定义nextj数组如下数组如下:- -1021t0=t1=at0t1=t1t2=aa开头的开头的k个字符个字符后面的后面的k个字符个字符11/29 nextj的含义的含义（2）nextj=- -1表示什么信息？表示什么信息？说明模式串说明模式串tj之前没有任何用于加速匹配的信息，下一趟应从之前没有任何用于加速匹配的信息，下一趟应从t的开头的开头即即j+ j=0开始匹配开始匹配。如如t=“abcd”，next0=next1=next2=next3=- -1。（1）nextj=k表示什么信息？表示什么信息？说明模式串说明模式串tj之前有之前有k个字符已成功匹配，下一个字符已成功匹配，下一趟趟应从

8、应从tk开始开始匹配。匹配。aaabaabnext2=1aaabaab0 1 2 3s:t:12/29由模式串由模式串t求求next值的算法：值的算法：13/29KMP算法：算法：14/29 设串设串s的长度为的长度为n，串，串t长度为长度为m。 在在KMP算法中求算法中求next数组的时间复杂度为数组的时间复杂度为O(m)，在后，在后面的匹配中因主串面的匹配中因主串s的下标不减即的下标不减即不回溯不回溯，比较次数可记为，比较次数可记为n，所以所以KMP算法算法平均时间平均时间复杂度为复杂度为O(n+m)。 最坏的最坏的时间复杂度为时间复杂度为O(n m)。KMP算法分析算法分析15/29 【

9、例（补充）例（补充）】 已知字符串已知字符串S为为“abaabaabacacaabaabcc”，模式串，模式串t为为“abaabc”，采用，采用KMP算法进行匹配，第一次出现算法进行匹配，第一次出现“失配失配”(si != tj)时，时，i=j=5，则，则下次开始匹配时，下次开始匹配时，i和和j的值分别是的值分别是 。 A.i=1，j=0 B.i=5，j=0 C.i=5，j=2 D.i=6，j=2说明：本题说明：本题为为2015年年全国考研题全国考研题 j012345tjabaabcnextj- -100112选C16/2917/29 设设目标串目标串s=“aaabaaaab”，模式，模式串串

10、t=“aaaab”。KMP模模式匹配式匹配过程。过程。j01234tjaaaabnextj- -10123求求t的的next：18/29j01234tjaaaabnextj- -10123a a a b a a a a bs:0 1 2 3 4 5 6 7 8a a a a bt:0 1 2 3 4 失败：失败：i=3j=3，j=next3=219/29j01234tjaaaabnextj- -10123a a a b a a a a bs:0 1 2 3 4 5 6 7 8a a a a bt:0 1 2 3 4 失败：失败：i=3j=2，j=next2=1i=3j=220/29j01234

11、tjaaaabnextj- -10123a a a b a a a a bs:0 1 2 3 4 5 6 7 8a a a a bt:0 1 2 3 4 失败：失败：i=3j=1，j=next1=0i=3j=121/29j01234tjaaaabnextj- -10123a a a b a a a a bs:0 1 2 3 4 5 6 7 8a a a a bt:0 1 2 3 4 失败：失败：i=3j=0，j=next0=- -1i=3j=022/29j01234tjaaaabnextj- -10123a a a b a a a a bs:0 1 2 3 4 5 6 7 8a a a a b

12、t:0 1 2 3 4 成功：成功：返回返回4因为因为j=- -1：i+;j+;23/29j01234tjaaaabnextj- -10123因为因为t3=t2=t1=t0=ai=3j=3i=3j=- -1i=3j=3将将si与与t3匹配匹配i=3j=2将将si与与t2匹配匹配i=3j=1将将si与与t1匹配匹配i=3j=0将将si与与t0匹配匹配i=3j=- -1将将si+1与与t0匹配匹配是不必要的是不必要的前面的匹配过程：24/29将将next改为改为nextval：j01234tjaaaabnextj- -10123nextvalj- -1- -1- -1- -13next1=0t1=

13、tnext1=t0=a nextval1=nextval0=- -1t4=b tnext4=a nextval4=next4用用nextval取代取代next，得到，得到改进的改进的KMP算法算法。 nextval0=- -1当当tj=tnextj时：时： nextvalj=nextvalnextj否则：否则： nextvalj=nextj25/29使用改进后的使用改进后的KMP算法示例：算法示例：j01234tjaaaabnextvalj- -1- -1- -1- -13a a a b a a a a bs:0 1 2 3 4 5 6 7 8a a a a bt:0 1 2 3 4 失败：失败：i=3j=3，j=nextval3=- -126/29a a a b a a a a bs:0 1 2 3 4 5