BZOJ 3670: [Noi2014]动物园

题目

题解

emmm题意理解极其困难，阅读题。做法就是首先用nxt数组求出cnt[i]，表示的是不考虑
重叠情况时的个数，再跑一次kmp,判断是否重叠。

代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 1000005;
const int mod = 1000000007;

int T,nxt[MAXN],cnt[MAXN];
char c[MAXN];

int main(){
    scanf("%d",&T);
    while(T--){
        long long ans=1;
        scanf("%s",c+1);
        int len=strlen(c+1);
        cnt[1]=1;
        for(register int i=2,j=0;i<=len;i++){
            while(j>0 && c[i]!=c[j+1]) j=nxt[j];
            if(c[i]==c[j+1]) j++;
            nxt[i]=j;
            cnt[i]=cnt[j]+1;
        }
        for(register int i=2,j=0;i<=len;i++){
            while(j>0 && c[i]!=c[j+1]) j=nxt[j];
            if(c[i]==c[j+1]) j++;
            while(j*2-i>0) j=nxt[j];
            ans=(ans*(cnt[j]+1))%mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}