KMP失效匹配.doc

KMP算法在子串匹配失效的时候，下一步并不是重新从子串的头部开始匹配，而是根据一下next函数计算出下一步应该从子串的什么部位开始匹配。举例如下： 红色为失效位置, ^表示的当前是指针位置，～表示此次匹配A串开始的位置。若是普通的匹配算法，当失效时，C串指针要回溯到头部，A串指针也要回溯到~的下一位。也就是下一步应该是从A的第二字符(e.g. b)和C的开头(e.g. a)开始匹配。如此循环 直到找到A串中的某一个位置可以匹配C串。然而从上面的匹配过程中，可以发现A和B的蓝色部分是第一步中已经确认匹配过的，上面四步的匹配其实可以看 作是蓝色部分的前半段与后半段在进行比较，而且前三步在蓝色部分就已经匹配失效了，所以这些比较是无谓的，因为它与父串A无关的，是属于子串C本身的信 息。只有第四步才涉及了与父串A中的字符(c)的比较。KMP算法正是利用这一点，它事先利用子串本身的信息就计算出当某一次匹配失效时，下一次应该继续匹配的位置。也就是当C串在最后一个b匹配失效时， 它省略了前三步(1,2,3)无谓的匹配，下一步比较将在d与c之间进行。这样父串A无需回溯，C串用一个next函数决定它将回溯的位置。所以 next函数至关重要，也是这个算法的关键。从上面的分析可以知道next函数是子串C本身的性质决定的，假设子串P = P0P1...Pn-1 next(j)=k(k=0): 当P的第 j+1个字符 匹配失败时, 在父串指针不回溯的情况下，下一步将与Pk+1比较。 当next(j)=k (k=0)时，子串指针回溯到Pk+1的位置，父串指针不变；当next(j)=-1时，子串指针回溯到头，父串指针前进一步； 在设计计算next值的程序的时候，我们没有必要每一步都去计算maximum(k)，可以用递归方式来做举个例子假设子串为P:abacabab, 且我们将要求的是b的next值, e.g. next[7]假设next[0~6]均为已知: next[0]=-1, next[1]=-1 , next[2]=0 , next[3]=-1 , next[4]=0 , next[5]=1 ,next[6]=2? abacababnext[6]=2可以说明P[0~2](蓝)与P[4~6](红)是一样的要求next[7]的值，我们可以找前6位(abacaba)中最长的前半段与后半段相等的子串，然后比较前半段子串的下一位是否和P[7]相等。在这个例子中, P[0~next[6]](e.g. P[0~2])就是这样的子串，接下来我们比较 c 和 b也就是P[next[6]+1](c)和P[7](b).若相等则 next[7] = next[6]+1若不等, 我们进一步找更短的前半段与后半段相等的子串,因为aba和aba是一样的, 要找abacaba中比abc短的这样的子串,相当于找aba 中的next[2]值是一样的.也就是next[next[6]]的值。然后再比较P[next[next[6]]+1]和P[7]是否等，若不等则继续找更短的这样子串在上的例子中 P[next[6]+1]=P[3](c) ，与P[7](b)不相等， 但是 P[next[next[6]]+1] = P[next[2]+1] = P[1](b), 与P[7](b)相等最后可以得到next[7] = next[next[6]]+1 = next[2]+1= 1;计算next值的代码：void calnext(char* P, int next[]){? next[0] = -1; //第一个元素的next总是-1, 因为根据(1) , 我们并找不到一个k比j=0小? for(int i=1; istrlen(P); i++){? int k = next[i-1]; //因为采用递归的方法, 为了计算next[i], 先记录下next[i-1] 而且假设next[i-1]已知? while(P[k+1]!=P[i]k=0){ // 递归? k = next[k];? }? if(P[k+1]==P[i]) //如果相等而结束, 则找到一对长度为k的前缀字串和后缀字串? next[i] = k+1; //增加了一个相同项? else? next[i] = -1; //其他情况? }} 匹配的代码：int find(char*T, char* pat){? int n = strlen(pat);? int *next = new int[n];? calnet(pat, next);? char *p=T, *q=pat;? int i=0;? while(*p!=\0(*(q+i)!=\0