文档介绍：KMP字符串匹配串类型的定义非数值处理的对象基本上是字符串数据串(string)(或称字符串)----由零个或多个字符组成的有限序列记为:s=‘a1a2...an’(n>=0)ai(1<=i<=n)是字母,数字或其它字符n称为串的长度,n=0的串称为空串(Nullstring)子串----串中任意个连续字符组成的子序列包含子串的串叫主串子串在主串中的位置----子串的第一个字符在主串中的序号串的例子例如:a,b,c,d四个字符串为a=‘BEI’,b=‘JING’c=‘BEIJING’,d=‘BEIJING’它们的长度分别为3,4,7,8a和b都是c和d的子串a在c和d中的位置都是1b在c中的位置是4,而b在d中的位置是5注意:单引号是为字符串区别于变量名而设,它不是字符串的内容称两个串是相等的---(S,T,pos)采用定长顺序存储结构,不依赖其他串操作的匹配算法:intIndex(SStringS,SStringT,intpos){//T是非空串,也称为模式,1<=pos<=S的长度。//若主串S中存在和模式T相同的子串,则返回它在主串//S中第pos个字符之后第一次出现的位置;否则返回0。i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//继续比较后续字符else{i=i-j+2;j=1;}//指针后退重新开始匹配}if(j>T[0])returni-T[0];//匹配成功elsereturn0;//匹配不成功}简单匹配算法的匹配过程示例例如T=“abcac”;S=“ababcabcacbab”第一趟匹配ababcabcacbab(i=3)abc(j=3)第二趟匹配ababcabcacbab(i=2)a(j=1)第三趟匹配ababcabcacbab(i=7)abcac(j=5)第四趟匹配ababcabcacbab(i=4)a(j=1)第五趟匹配ababcabcacbab(i=5)a(j=1)第六趟匹配ababcabcacbab(i=11)abcac(j=6)成功!简单匹配算法的复杂度分析设n=StrLength(S);m=StrLength(T);最好情况的复杂度为O(n+m),如T=“STING”S=“ASTRINGSEARCHINGEXAMPLECONSISTINGOFSIMPLETEXT”最坏情况的复杂度为O(n*m),如T=“00000001”S=“00000000000000000000000000000000000000000000000001”模式匹配的一种改进算法(KMP算法)KMP算法的改进在于:每一趟匹配过程中出现字符比较不等时,不需要回朔i指针只要利用已经“部分匹配”结果,调整j指针,即将模式向右滑动尽可能远的一段距离,(i=3)abc(j=3)第二趟匹配ababcabcacbab(i=3->7)abcac(j=1->5)第三趟匹配ababcabcacbab(i=7->11)(a)bcac(j=2->6)显然算法复杂度为O(n+m)KMP算法的基本思想(一)假设主串为S=“s1s2...sn”,模式串为T=“t1t2...tm”我们要解决的问题是:当“失配”(sitj)时,模式串T”向右滑动”的可行距离有多远;或者说,下一步si应该与模式串中的哪个字符比较?可以推断:答案将完全取决于模式串,而与主串无关因此,可以预先为模式串设定一个数组next[j],当“失配”(sitj)时,i不变,j改为next[j]前面例子的next[j]是:ext[j]01112KMP算法的匹配过程示例另一个模式串的例子是:任选一主串举例如下:第一趟acabaabaabcacaabc(i=1..2)ab (j=2,next[2]=1)第二趟acabaabaabcacaabc(i=2..2)a(j=1,next[1]=0)第三趟acabaabaabcacaabc(i=3..8)abaabc(j=6,next[6]=3)第四趟acabaabaabcacaabc(i=6..14)(ab)aabcac(j=9,成功)ext[j]011223126=8-next[6]+1KMP算法的基本思想(二)一般情况下,模式串的next函数的定义如下:0当j=1时next[j]=max{k|1<k<j且“t1...tk-1”=“tj-k+1...tj-1”}1其他情况如:ext[j]01122312