BZOJ3670: [Noi2014]动物园【KMP】

3670: [Noi2014]动物园

【题目描述】

传送门

【题解】

这题题目已经提醒你了,是KMP,但是我们怎么知道这个Num呢?
我们要枚举一个k,表示能匹配的最长长度,因为长度不能超过一半。
然后我们用cnt[i]来记录1~i,中能自己匹配的个数,最后Ans*(cnt[i]+1)。
但是你会发现每次枚举k,时间效率很低,所以我们可以向j一样枚举k,就可以了。

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;
int n,pre[1000005],cnt[1000005];
LL Ans;
char s[1000005];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("3670.in","r",stdin);
    freopen("3670.out","w",stdout);
    #endif
    int T;
    for(scanf("%d",&T);T;T--){
        scanf("%s",s+1);Ans=1;n=strlen(s+1);cnt[1]=1;
        for(int i=2,j=0,k=0;i<=n;i++){
            while(j&&s[i]!=s[j+1]) j=pre[j];
            if(s[i]==s[j+1]) j++;
            pre[i]=j;cnt[i]=1+cnt[j];

            while(k&&s[i]!=s[k+1]) k=pre[k];
            if(s[i]==s[k+1]) k++;
            while(k*2>i) k=pre[k];
            Ans=(Ans*(cnt[k]+1))%MOD;
        }
        printf("%lld\n",Ans);
    }
    return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部