定义字符串的前 \(i\) 个字符组成的字符串中一最大子串 \(T\) 即使前缀也是后缀，且 \(|T|\leq i/2\) ，则定义 \(num[i]=|T|\) ，求 \(num[i]+1\) 之积 \(mod\) 1000000007。 \(|S|\leq 10^6\) 。
熊猫：“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作 \(nxt[i]\) 。”
根据 \(num\) 数组的定义， \(num[i]\) 表示在 \(nxt[nxt[...]]\leq i/2\) 之后在跳 \(num[i]\) 次 \(nxt\) 就会等于0
举个例子：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| s[i] | a | b | a | b | a | b | a | b |
| nxt[i] | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
\(nxt[7]=5\) 由于有交叉， \(nxt[7]=nxt[nxt[7]]=nxt[5]=3\) ,表示 \(s[1...3]=s[5...7]\)， \(num[7]++\) 。同理在 \(nxt[7]=3\) 时 \(num[7]++\) 。
所以这题只用先跑一遍KMP，之后用 \(nxt\) 数组回溯即可。
考虑到时间复杂度有可能退化，所以在每一次 \(j\) 指针计数结束后不还原，就可以使之后的 \(nxt\) 更快接近 \(i/2\) 。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,nxt[1000005],num[1000005],slen;
char s[1000005];
ll ans;
int main()
{
scanf("%d",&n);
while(n)
{
n--;
memset(num,0,sizeof(num));
ans=1;
scanf("%s",s+1);
slen=strlen(s+1);
num[1]=1;
for(int i=2,j=0;i<=slen;++i)
{
while(j>0 && s[i]!=s[j+1])
j=nxt[j];
if(s[i]==s[j+1])
++j;
nxt[i]=j;
num[i]=num[j]+1;
}
for(int i=2,j=0;i<=slen;++i)
{
while(s[i]!=s[j+1] && j>0)
j=nxt[j];
if(s[i]==s[j+1])
++j;
while(j*2>i)
j=nxt[j];
ans=ans*(num[j]+1)%1000000007;
}
printf("%lld\n",ans);
}
}