学步园

题意:

给出一个字符串,求其所有前缀串为模式串时匹配成功的次数.

思路:

就和AC自动机那题处理模式串重叠的方法一样,每到一处,回溯到根检查一遍.

#include <cstdio>
using namespace std;
const int MAXW = 200005;
const int MOD = 10007;
char W[MAXW];
int n;
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;
    }
    /*for(int i=0;i<n;i++)
        printf("next[%d] %d\n",i,next[i]);*/
}

int kmp(char *B, int *next)
{
    long long ret = 0;
    for(int i=0; B[i]; i++)
    {
        ret++;
        int tmp = next[i];
        while(tmp!=-1)
        {
            ret++;
            tmp = next[tmp];
        }
        ret %= MOD;
    }
    return ret;
}

int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        scanf("%s",W);
        prekmp(W,next);
        printf("%d\n",kmp(W,next));
    }
}