现在的位置: 首页 > 综合 > 正文

[POJ3461] Oulipo[KMP基础]

2019年04月05日 ⁄ 综合 ⁄ 共 3439字 ⁄ 字号 评论关闭

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(也就是kmpj位置(已经匹配上的最末端))就等于prekmpj的值(左端右端)

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));
    }
}

抱歉!评论已关闭.