§4 串
§4.1 串的匹配
子串的定位操作称为串的模式匹配,是各种串处理中最重要的操作.在主字符串S中查找模式字符串P,若在主串中找到等于模式串的子串,称为匹配成功,返回与模式串第一个相等的字符在主串中的序号；若匹配不成功,则返回0. §4.1.1 串的简单匹配
串的简单匹配,基本思想是：从主串的第一个字符起和模式串的第一个字符比较,若相等,则继续逐个比较后续的字符,否则从主串的第二个字符起再重新和模式串的字符比较.依此类推,直至模式串的每个字符依次和主串中的一个连续的字符序列相等,则为匹配成功……
【例4-1-1】： 主串：a b a b c a b c a c b a b
匹配串：a b c a c ↓i =3
第一趟匹配： a b a b c a b c a c b a b
a b c
↑j =3 ↓i=2
第二趟匹配： a b a b c a b c a c b a b a ↑j=1
↓i=7
第三趟匹配： a b a b c a b c a c b a b a b c a c ↑j=5 ↓i=4
第四趟匹配： a b a b c a b c a c b a b a ↑j=1 ↓i=5
第五趟匹配： a b a b c a b c a c b a b a ↑j=1
↓i=11
第六趟匹配： a b a b c a b c a c b a b a b c a c ↑j=6
这种算法易于理解,在某些场合效率也较高.但当主串为‘0000000000000000000000000 00000000000000000000000001’,模式串为‘00000001’时,由于模式串中前7各字符均为‘0’,主串中前50各字符均为‘0’,每趟比较都在模式串的最后一个字符出现不等,此时需将指针i回溯到i-6的位置上,并从模式的第一个字符开始重新比较.直到匹配成功,指针i需回溯43次.这经常出现在主串中存在多个子串和模式串“部分匹配”的情况下,例如01串（字符串由0、1组成）.
§4.1.2 串的KMP匹配算法
这种改进的算法是由D.E.Knuth、V.R.Pratt和J.H.Morris三人同时发现的,所以称为KMP算法.
（一）KMP算法的基本思路
KMP算法每当一趟匹配过程中发现字符不等时,不需回溯i指针,而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后,继续进行比较. 先回顾简单匹配的算法,从例4-1-1可以看出,在第三趟匹配中,当i=7、j=5字符比较不等时,又从i=4、j=1重新比较.而在i=4和j=1,i=5和j=1,以及i=6和j=1这三次比较都是不必要的.
因为从第三趟部分匹配的结果可以看出,主串中第4、5、6个字符必然是’b’、’c’、’a’（即模式串中第2、3、4个字符）.因为模式串中第一个字符是a,因为它无需和这三个字符进行比较,所以仅需将模式串向右滑动三个字符的位置进行比较.同理,在第一趟匹配中出现字符不等时,仅需将模式串向右移动2个字符的位置继续进行i=3、j=1时的字符比较.由此,整个过程指针i没有回溯,如下所示.
↓i=3
第一趟匹配：a b a b c a b c a c b a b
a b c
↑j=3
↓i=7
第二趟匹配：a b a b c a b c a c b a b
a b c a c
↑j=5
↓i=11
第三趟匹配：a b a b c a b c a c b a b
a b c a c
↑j=6
KMP算法的基本思想是:
在匹配过程中,当 Si≠Pj 时,应在模式串P的开头和主串S紧靠i之前找到相等的最大子串,子串长度为k –1,如图所示：
i S
P
k k-1 j
然后将模式串向右滑动,比较Si和Pk是否相等. 对于KMP算法,需要解决的问题首先是：当匹配过程产生“失配”,模式串“向右滑动”可行多远？换句话说,当主串中第i个字符与模式串中第j个字符“失配”（即不相等）时,主串中第i个字符应与模式串中哪个字符再比较？
（二）求证k仅与模式串相关
设主串为S,模式串为P.假设当主串中第i个字符与模式串中第j个字符“失配”时,主串的第i个字符应与模式串的第k个字符继续比较,则模式串中前j个字符必须满足下列关系：
‘P1P2……Pk-1’＝‘Si - k+1Si - k+2……Si-1’ （1）
{匹配串P的前k-1个字符与主串中第i个字符前的k-1个字符相等} 而已经得到“部分匹配”的结果是：
‘Pj-k+1Pj-k+2……Pj-1’＝‘Si-k+1Si-k+2……Si-1’ （2）
{匹配串P第j个字符前的k-1个字符与主串中第i个字符前的k-1个字符相等} 由（1）和（2）,可以推出下式：
‘P1P2……Pk-1’＝‘Pj-k+1Pj-k+2……Pj-1’
即模式串中前k-1个字符与第j-k+1到j-1个字符相等,即k仅与模式串有关,与主串．．无关. ．．
（三）next数组
因此,我们可以设next数组,令next[j]=k,则next[j]表明当模式中第j个字符与主串相应字符“失配”时,主串中该字符重新与模式串中进行比较的字符的位置.
Next数组的定义：
0 当 j=1时
next[j]= Max { k | 1 1 其它情况 【例4.1.2_1】 j 模式串 next [ j ] Next数组怎样具体求得,我们这里先放一下,先看看在设了next数组后KMP匹配的算法,这可能将更有利于理解. （四）KMP算法 匹配可如下进行： ① 指针i和j分别指示主串和模式串中正待比较的字符,令i和j的初值皆为1. ② 若在匹配过程中si = pi ,则i和j分别增1,否则j再退到下一个next值的位置, 依此类推,直至下列可能： 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2
高中信息技术竞赛班数据结构专项培训教程04串教案
