洛谷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=
0;
for(ll i=
2;i<=len;i++
)
{
while(j&&a[i]!=a[j+
1]) j=
next[j];
if(a[i]==a[j+
1]) j++
;
next[i]=
j;
cnt[i]=cnt[j]+
1;
//递推公式
}
}
int main()
{
scanf("%d",&
T);
while(T--
)
{
memset(cnt,0,
sizeof(cnt));
memset(next,0,
sizeof(next));
ans=
1;
//初始化
scanf(
"%s",a+
1);
len=strlen(a+
1);
cnt[1]=
1;
//初始化
kmp();
ll j=
0;
for(ll i=
2;i<=len;i++
)
{
while(j&&a[i]!=a[j+
1]) j=
next[j];
if(a[i]==a[j+
1]) j++
;
while((j<<
1)>i) j=next[j];
//不断缩小范围直到小于原前缀i长度的一半
ans*=(cnt[j]+
1);
//统计ans
ans%=
mod;
}
printf("%lld\n",ans);
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9806559.html
相关资源：JAVA上百实例源码以及开源项目
