ps下文的next和fail是一个东西
注意题目描述中对next的讲解
“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。”
num数组：对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀的字符串的数量
一个性质：当前串的前缀（后缀）的前缀（后缀）也是当前串的前缀（后缀）
将前缀（后缀）的next的数组作为指父亲的边会建成一棵树
num其实就是树上结点的深度？
还有点差别……题目中的前缀和后缀是不能重叠的
先把深度记为ans
考虑当前串的一个不大于它长度的1/2的前缀（后缀）子串，这个子串的ans其实是i的num
默上板子之后暴跳倍增找一下上文所述的子串
#include<bits/stdc++.h>
using namespace std;
char s[2000000];
int fail[2000000][37],ans[2000000];
int mod=1e9+7;
int main()
{
int n;
cin>>n;
while(n--)
{
memset(ans,0,sizeof(ans));
memset(fail,0,sizeof(fail));
cin>>s+1;
int ls=strlen(s+1);
int j=0;
ans[1]=1;
for(int i=2;i<=ls;i++)//i如果从1开始会使i和j始终指在同一点上，匹配的时候要错开一位
{
while(j&&s[j+1]!=s[i]) j=fail[j][0];
if(s[j+1]==s[i]) j++;
fail[i][0]=j;
ans[i]=ans[j]+1;
}
for(int i=1;i<=ls;i++)
for(int k=1;k<=30;k++)
fail[i][k]=fail[fail[i][k-1]][k-1];
long long answer=1;
for(int i=1;i<=ls;i++)
{
int j=i;
for(int k=30;k>=0;k--)
if(2*fail[j][k]>i&&fail[j][k]) j=fail[j][k];
j=fail[j][0];
answer*=(long long)(ans[j]+1);
answer%=mod;
}
cout<<answer<<"
";
}
}
不是很明白为什么会t，感觉复杂度挺对的其实，，，
#include<bits/stdc++.h>
using namespace std;
char s[2000000];
int fail[37][2000000],ans[2000000];
int mod=1e9+7;
int main()
{
register int n;
cin>>n;
while(n--)
{
scanf("%s",s+1);
register int ls=strlen(s+1);
register int j=0;
ans[1]=1;
for(register int i=2;i<=ls;i++)//i如果从1开始会使i和j始终指在同一点上，匹配的时候要错开一位
{
while(j&&s[j+1]!=s[i]) j=fail[0][j];
if(s[j+1]==s[i]) j++;
fail[0][i]=j;
ans[i]=ans[j]+1;
}
for(register int k=1;k<=20;k++)
for(register int i=1;i<=ls;i++)
fail[k][i]=fail[k-1][fail[k-1][i]];//不能放到上面的循环里面求，fail1求不出来
long long answer=1;
for(register int i=1;i<=ls;i++)
{
register int j=i;
for(register int k=20;k>=0;k--)
if(2*fail[k][j]>i&&fail[k][j]) j=fail[k][j];
j=fail[0][j];
answer*=(long long)(ans[j]+1);
answer%=mod;
}
cout<<answer<<"
";
}
}
玄学优化一下，
1.按照题解里把倍增二维反过来莫名其妙快了好多，，不懂为什么
2.读入字符串要比读入字符快（？）
#include<bits/stdc++.h>
using namespace std;
char s[2000000];
int fail[2000000],ans[2000000];
int mod=1e9+7;
int main()
{
register int n;
cin>>n;
while(n--)
{
scanf("%s",s+1);
register int ls=strlen(s+1);
register int j=0;
ans[1]=1;
for(register int i=2;i<=ls;i++)//i如果从1开始会使i和j始终指在同一点上，匹配的时候要错开一位
{
while(j&&s[j+1]!=s[i]) j=fail[j];
if(s[j+1]==s[i]) j++;
fail[i]=j;
ans[i]=ans[j]+1;
}
long long answer=1;
j=0;
for(register int i=2;i<=ls;i++)
{
while(s[j+1]!=s[i]&&j) j=fail[j];
if(s[j+1]==s[i]) j++;
if(j<<1>i&&j) j=fail[j];
answer*=(long long)(ans[j]+1);
answer%=mod;
}
cout<<answer<<"
";
}
return 0;
}
O(n)正解做法，
这个过程本质上是再找一个前缀（后缀），同时要求长度不超过1/2
这个过程其实和kmp板子的匹配过程还是很相似的？
那么j不从头找了
考虑每一次i+1后字符串多了一位字符
此时的前后缀为
1.上一次匹配的j+1（新加的一位和前面匹配成功）
2.跳fail直到匹配成功或调到头了（新加的一位和前面匹配失败）
因为原来的j小于原来的i/2，那么j肯定也小于（i+1）/2
最多匹配成功多加了一位，特判一下j需不需要-1就可以啦~