![【题解】洛谷P2375 [NOI2014] 动物园(KMP) 【题解】洛谷P2375 [NOI2014] 动物园(KMP)](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
洛谷P2375:https://www.luogu.org/problemnew/show/P2375
思路
这道题可以说是完全刷新了本蒟蒻对KMP的理解
感觉对next数组的理解上升到一个新的高度
首先题目给出了next数组的定义
关于整个字串 next[len]为前缀与后缀相同的最长长度
我们给出一张从你谷题解中扒下来的图
我们可以观察到对于整个长度为len的字串a
next[len],next[next[len]],next[next[next[len]]]...全部都是满足前缀与后缀相同的子串
但是仅仅把这些加起来是不足以解决这道题的
因为题目要求的是不重叠 因此我们需要判断这个子串长度是否大于此前缀i长度的一半 我们设cnt数组为有重叠的 再从中筛选
因为考虑到时间效率 我们需要用求next数组的方法求num数组
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define maxn 1000010
#define mod 1000000007
ll cnt[maxn],next[maxn];
ll len,ans;
char a[maxn];
int T;
void kmp()
{
ll j=;
for(ll i=;i<=len;i++)
{
while(j&&a[i]!=a[j+]) j=next[j];
if(a[i]==a[j+]) j++;
next[i]=j;
cnt[i]=cnt[j]+;//递推公式
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(cnt,,sizeof(cnt));
memset(next,,sizeof(next));
ans=;//初始化
scanf("%s",a+);
len=strlen(a+);
cnt[]=;//初始化
kmp();
ll j=;
for(ll i=;i<=len;i++)
{
while(j&&a[i]!=a[j+]) j=next[j];
if(a[i]==a[j+]) j++;
while((j<<)>i) j=next[j];//不断缩小范围直到小于原前缀i长度的一半
ans*=(cnt[j]+);//统计ans
ans%=mod;
}
printf("%lld\n",ans);
}
}