【BZOJ3670】【NOI 2014】动物园(KMP)

本文主要是介绍【BZOJ3670】【NOI 2014】动物园(KMP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3670
题解：
以前写过一次但不是很懂，所以重新写了一下
首先构造一个cnt数组表示前缀等于后缀的子串的数目
那么cnt【i】=cnt【next【i】】+1，可以在求next同时求出来
cnt【1】=1 // 只有它本身
求 num【i】时只需找到第一个长度小于 i / 2 的子串即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MOD 1000000007
using namespace std;
int nxt[1000001],cnt[1000001],len;
int main()
{int T;int j,p; scanf("%d",&T);char s[1000001];while(T--){cnt[1]=1;j=0;scanf("%s",s+1);len=strlen(s+1);long long ans=1;for(int i=2;i<=len;i++){while(j&&s[j+1]!=s[i]) j=nxt[j];j+=(s[j+1]==s[i]);p=nxt[i]=j;cnt[i]=cnt[j]+1;while(2*p>i) p=nxt[p];ans=ans*(cnt[p]+1)%MOD;}printf("%lld\n",ans);}
}

但是这个会TLE
因为在找第一个不重叠子串的时候是O（n）的
所以类比KMP算法中的步骤
可以近似O（1）的得到这个位置

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long longconst int N=1000100;
const int mod=1e9+7;int nxt[N],cnt[N];
LL num[N];void Get_nxt(char *s,int nxt[])
{int lens=strlen(s+1);int j=0;nxt[1]=0;cnt[1]=1;for(int i=2;i<=lens;i++){while(j&&s[j+1]!=s[i]) j=nxt[j];j+=(s[j+1]==s[i]);nxt[i]=j; cnt[i]=cnt[nxt[i]]+1;}
}LL KMP(char *s)
{LL ans=1;int j=0;int lens=strlen(s+1);for(int i=2;i<=lens;i++){while(j&&s[j+1]!=s[i]) j=nxt[j];j+=(s[j+1]==s[i]);while((j<<1)>i) j=nxt[j];ans=(ans*(cnt[j]+1))%mod;}return ans;
}int main()
{int T;char s[N];cin>>T;while(T--){scanf("%s",s+1);Get_nxt(s,nxt);printf("%lld\n",KMP(s));}return 0;
}