KMP
[对于理解来说重要的语句] [理解与注释] [非重要语句]
假如,A="abababaababacb",B="ababacb",我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符(j当然越大越好),现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时,i和j各加一;什么时候j=m了,我们就 说B是A的子串(B串已经整完了),并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1],KMP的策略是调整j的位置 (减小j值)使得A[i-j+1..i]与B[1..j]保持匹配(i和j总是指向已经匹配的末尾,比较i+1和j+1位置)且新的B[j+1]恰好与A[i+1]匹配(从而使得i和j能继续增加)。我们看一看当 i=j=5时的情况。
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
此 时,A[6]<>B[6]。这表明,此时j不能等于5了,我们要把j改成比它小的值j',{使得A的后面部分和B的前面部分是相等的,但是因为到目前为止,AB已经完全匹配,也就变成B的前面和B的后面相等}.j'可能是多少呢?仔细想一下,我们发现,j'必须 要使得B[1..j]中的头j'个字母和末j'个字母完全相等(这样j变成了j'后才能继续保持i和j的性质)。这个j'当然要越大越好。在这里,B [1..5]="ababa",头3个字母和末3个字母都是"aba"。而当新的j为3时,A[6]恰好和B[4]相等。于是,i变成了6,而j则变成了 4:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
从 上面的这个例子,我们可以看到,新的j可以取多少与i无关,只与B串有关。我们完全可以预处理出这样一个数组P[j],表示当匹配到B数组的第j个字母而 第j+1个字母不能匹配了时,新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。{减小j,又因为B[j+1]要和A[i+1]比较,而i是不变的,所以就好像B向后移动了一样}
再后来,A[7]=B[5],i和j又各增加1。这时,又出现了A[i+1]<>B[j+1]的情况:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
由于P[5]=3,因此新的j=3:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
这时,新的j=3仍然不能满足A[i+1]=B[j+1],此时我们再次减小j值,将j再次更新为P[3]:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
现在,i还是7,j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样,j必须减小到P[1],即0://这里的P[1] = 0;是规定的?A[i+1]和B[j+1]比较,等1再往后退就要比较A[i+1]==B[0+1]了,因此转移时P[1] = 0.
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
终于,A[8]=B[1],i变为8,j为1。事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如A[8]="d"时)。因此,准确的说法是,当j=0了时,我们增加i值但忽略j直到出现A[i]=B[1]为止。
这个过程的代码很短(真的很短),我们在这里给出:
j:=0; for i:=1 to n do begin //j==0时忽略j的转移,直接比较 while (j>0) and (B[j+1]<>A[i]) do j:=P[j]; if B[j+1]=A[i] then j:=j+1; if j=m then begin writeln('Pattern occurs with shift ',i-m); j:=P[j];//此时必有B[j+1]<>A[i],不要这句也可以,加上可以简化一些 end; end;
最后的j:=P[j]是为了让程序继续做下去,因为我们有可能找到多处匹配。
这个程序或许比想像中的要简单,因为对于i值的不断增加,代码用的是for循环。因此,这个代码可以这样形象地理解:扫描字符串A,并更新可以匹配到B的什么位置。
二,如何快速预处理P数组。
Matrix67原创
转贴请注明出处
求解next
void prekmp(char *B, int *next) { next[0] = -1;//这是规定 int j = -1; for (int i = 1; B[i]; i++) { while (j != -1 && B[i] != B[j + 1]) j = next[j]; if (B[i] == B[j + 1]) j++; next[i] = j; } }
/*****************************************************
i对应的位置(原B串的末尾)的next(也就是kmp时j位置(已经匹配上的最末端))就等于prekmp里j的值(”左端”配”右端”)
1:if (B[i] == B[j + 1]) j++;那么有B[i] == B[j]说明目前j的值就是原B串中i对应位置对应左端已匹配部//分的最后一个位置,即要跳转到的位置.
2:if (B[i] != B[j + 1])说明j == -1(不然前面的while不会跳出), next[i] = -1;也是满足规则的
和kmp相比,不去判断子串是否结束(当然也不可能结束!),而是记录i位置已经匹配上的子串最末位置.其他都一样,是kmp(B, B, next).
*******************************************************/
#include <cstdio> using namespace std; const int MAXW = 10005; const int MAXT = 1000005; char W[MAXW], T[MAXT]; int next[MAXW]; void prekmp(char *B, int *next) { int j = -1; next[0] = -1; for(int i=1; B[i]; i++) { while(j != -1 && B[j+1] != B[i]) j = next[j]; if(B[i] == B[j+1]) j++; next[i] = j; } } int kmp(char *A, char *B, int *next) { int j = -1,ret = 0; for(int i=0; A[i]; i++) { while(j != -1 && A[i] != B[j+1]) j = next[j]; if(A[i] == B[j+1]) j++; if(!B[j+1]) { ret++; j = next[j]; } } return ret; } int main() { int cas; scanf("%d",&cas); while(cas--) { scanf("%s%s",W,T); prekmp(W,next); printf("%d\n",kmp(T,W,next)); } }