BZOJ3670: [Noi2014]动物园

传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=3670

Solution

求next数组时可以顺便求出每个前缀的border的个数,记为cnt.统计答案的时候强制使匹配长度小于i/2就可以了.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005,mod=1000000007;
int T,n;
long long ans;
int next[N],cnt[N];
char s[N];
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%s",s+1);
        n=strlen(s+1);
        memset(next,0,sizeof next);
        memset(cnt,0,sizeof cnt);
        ans=cnt[1]=1;
        for (int i=2,j=0;i<=n;i++){
            while (s[i]!=s[j+1]&&j) j=next[j];
            if (s[i]==s[j+1]) j++;
            next[i]=j; cnt[i]=cnt[j]+1;
        }
        for (int i=2,j=0;i<=n;i++){
            while (j&&s[i]!=s[j+1]) j=next[j];
            if (s[i]==s[j+1]) j++;
            while ((j<<1)>i) j=next[j];
            (ans*=cnt[j]+1)%=mod;
        }
        for (int i=1;i<=n;i++)
            printf("%d ",next[i]);
        printf("\n");
        for (int i=1;i<=n;i++)
            printf("%d ",cnt[i]);
        printf("%lld\n",ans);
    }
}