KMP算法(原创)

第四章字符串模式匹配算法什么是模式匹配？在一般的编辑软件中，经常要遇到在一个给定的文本中查找一个特定的字符串的问题，这就是字符串匹配，也称模式匹配。设P是一个模式字符串(简称模式)，其长度为m；s是一个正文字符串(简称正文)，其长度为n。通常认为nm简单算法(Brute-Force算法)算法描述：从正文s和模式p的第一个字符出发，将s和p的字符依次逐个进行比较，如果p中的所有字符均与s中的对应字符匹配，则说明匹配成功；如果在比较过程中发现了一个字符不匹配，则将模式p沿正文s向后移动一个字符的位置，然后再从p的第一个字符开始与中的对应字符逐个进行比较。以此类推，直到匹配成功或到达的末段为止。(2)Brute-Force算法的实现intString::FindSubstr(constString&t,intstart)const{inti=start,j=0,v;while(isize&&jt.size){if(str[i]==t.str[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j=t.size-1)v=i-t.size+1;elsev=-1;returnv;}模式匹配的KMP算法基本思想：当模式p与正文s进行比较的过程中发现不匹配时，找到一种模式p沿正文s向后移动的规则，以便使得正文s中失去匹配的字符以前的字符不再参与比较，即只从当前失去匹配的字符开始与模式p中的字符继续依次进行比较，并且又不错过模式被发现的机会。示例：算法分析假设正文为‘s0s1……sn-1’，模式为‘p0p1……pm-1’，要实现改进算法，也就是要解决下述问题：当匹配过程中产生失配时(即si!=pj)，模式“向右滑动”可行的距离有多远，换句话说，当正文中第i个字符与模式中第j个字符“失配”时，正文中第i个字符应与模式中哪个字符相比较？假设此时应与模式中第k个字符继续比较，其中k应具有以下两个性质：1、kj，因为当失配时必然使模式p向后移，从而导致kj。移的幅度越小，k与j相差越小。2、k应取所有可能值中的最大值，因为取最大值就意味着移的幅度最小，也就避免错过成功匹配的机会。根据这个假设，必然使得下式成立：‘p0p1……pk-1’=‘si-ksi-k+1……si-1’(1)而已经得到的“部分匹配”的结果是：‘pj-kpj-k+1……pj-1’=‘si-ksi-k+1……si-1’(2)(2)式的由来是：当初正文中的第i个字符与模式中的第j个字符失配时，说明两者之前的j个字符肯定是一样的，而kj，所以前k个字符也是相同的。这就得出(2)式。由(1)(2)两式便可得：‘p0p1……pk-1’=‘pj-kpj-k+1……pj-1’(3)(3)式的结论可如下描述：在模式p中，前k个字符与第j个字符之前的k个字符相同。设next[j]表示：当模式中第j个字符与正文中相应字符“失配”时，在模式中重新和正文中该字符进行比较的字符的位置。并令next[j]=k。Next数组的完整定义如下：Max{k|0kj且‘p0p2……pk-1’=‘pj-kpj-k+1……pj-1’}当此集合不为空时next[j]=-1当j=0时；0其他情况Next[0]=-1表示当模式p的第0个字符失去匹配时应将p沿正文方向右移一个位置，也即使p的第一个字符与正文s的下一个字符进行比较。利用next数组进行模式匹配示例：如何预先求得next数组值首先要明确一点：next数组的求值只与模式p有关，而与具体的正文s无关。我们可用递推的方法求next数组值。假设已求得next[j]=k，根据定义可得‘p0p2……pk-1’=‘pj-kpj-k+1……pj-1’那么next[j+1]=？1、若pk=pj，则表明‘p0p1……pk’=‘pj-kpj-k+1……pj’，并且不可能存在k’k满足上式，那么next[j+1]=k+1式1也就是：next[j+1]=next[j]+12、若pk!=pj，则表明‘p0p1……pk’!=‘pj-kpj-k+1……pj’这时如何求next[j+1]呢？有两种可能情况转化法式1的结论可这样描述：何时的k使得pk=pj，就用此时的k代入式1。而现在的k是pk!=pj，因此必须要换成另外一个“k”，并设它为k2，以使得pk2=pj。问题又出来了：k2如何得来？如图：要使得k转为k2，实际上就是将p往右移，移动后p’的j对应p的k2。00jjj-k+1kP’Pk2，到底是多少首先取决于另一个前提条件：‘p0p1……pk2-1’=‘pj-k2pj-k2+1……pj-1’如图：实际上，k2=next[k]000jjjj-k+1kkk2k-k2+1p1p2p3•那么，满足了这个前提条件，是否就满足pk2=pj了呢？•显然两者互不相干。也就是说，仅移动一次不一定满足pk2=pj。•如果移动一次后得到k2仍然不满足pk2=pj，就要按照前提条件再移动一次。•依次类推，直到pkn=pj,或kn=0为止。•此时有：next[j+1]=kn+1•而kn=next[kn-1]•k1=k=next[j]由于，knkn-1……k1=kj因此，当需要求next[j+1]时，next[j]、next[k1]、next[k2]……next[kn]都已经求出来了。