KMP子符串匹配

代码里已经码的比较清楚了.....

时间复杂度 $O(n)$

C++ 代码

#include<bits/stdc++.h>
#define N 1000010
#define ll long long
#define next _next
using namespace std;
/*
    显然当时考试的时候没有考虑到如果是1e6个a,暴力往回跳是会超时的...(递归过深)
    经过分析我们发现,如果不考虑重叠的情况,那此时的num数组是可以直接递推求出.
    因为一个子串的所有相同的前后缀可以表示为{next[i],next[next[i]],next[next[next[i]]]....}.
    一个显而易见的结论就是num[i]=num[next[i]]+1.(不考虑重叠的情况) 
    然后考虑去重.
    我们都知道next[i]一定小于i.
    那么如果我们已经从i这个位置往回跳next,跳了若干次后,发现此时的next小于了i的一半,那这个next
    就是我们要的不重叠的总数,即num[i]=此时的next.
    当然,我们还是遇到这个问题,如果来1e6个a,还是会面临超时.
    考虑优化,其实我们需要优化的核心是减少递归次数.
    我们就再求一遍next数组,在求时,顺带递归,如果当前的j满足小于i的一半,那这就是当前的答案. 
*/
const ll mod=1e9+7;
char str[N];
int len,n,next[N];
ll num[N],ans;
inline void solve()
{
    len=strlen(str+1);
    int k=0;
    next[1]=0,num[1]=1;
    for(int i=2;i<=len;i++){
        while(k&&(str[k+1]!=str[i]))
            k=next[k];
        if(str[k+1]==str[i])
            k++;
        next[i]=k;
        num[i]=num[k]+1;
        //num数组是可以直接递推求出(注意此时的num数组还未去除含有重叠公共前后缀的数目) 
    }
    k=0;
    for(int i=2;i<=len;i++){
        while(k&&(str[k+1]!=str[i]))
            k=next[k];
        if(str[k+1]==str[i])
            k++;
        while(k*2>i&&next[k])
            k=next[k];
        ans=(ans*(ll)(num[k]+1))%mod;
    }
}
int main()
{
//  freopen("zoo.in","r",stdin);
//  freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    while(n--){
        ans=1;
        memset(next,0,sizeof(next));
        memset(num,0,sizeof(num));
        scanf("%s",str+1);
        solve();
        printf("%lld\n",ans);
    }
    return 0;
}