题目大意
求出字符串$S$前$i$个字符组成的子串中，前缀=后缀且前缀后缀不重叠的子串个数。
初步想法
题目都明显地提示了KMP，就应该按照求$Next$数组的思路思考。
如果不考虑不重叠，求出前缀=后缀的子串个数，应该怎么做？
显然不可能是$Next$数组，$Next$数组求的是长度而不是子串个数。
那怎么求出个数呢？
注意到我们求$Next$数组实际上就是不断地再递归本身，不断地递归到前缀=后缀的地方观察是否匹配。
等等刚刚我说了什么？前缀=后缀！
没错，那么实际上个数就是经过多少次$j=Next[j]$能够使$j$变成0。
我们用$Depth$数组记录该信息，那么$S[i]$与$S[j]$匹配时，$Depth[i]=Depth[j]+1$
这样我们就解决了不重叠的个数。
问题还没有结束，如果重叠怎么办？
其实很简单，如果重叠就说明当前前缀=后缀的长度太长，需要缩短，那么不断地执行$j=Next[j]$，直到前缀与后缀不重叠即$j\times2\le i$为止，那么当前的$Depth$即为答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,Next[1000005],Depth[1000005];
LL ans=1,mod=1000000007;
void Get_Next(string s) {
int i=1,j=0;
Next[1]=0;
Depth[i]=0;
while(i<=s.length()-1)
if(j==0||s[i]==s[j]) {
Next[++i]=++j;
Depth[i]=Depth[j]+1;
} else j=Next[j];
}
void Get_Ans(string s) {
int i=1,j=0;
while(i<=s.length()-1)
if(j==0||s[i]==s[j]) {
i++,j++;
while(j!=0&&((j-1)<<1)>(i-1))j=Next[j];
if(j!=0)ans=ans*(LL)(Depth[j]+1)%mod;
} else j=Next[j];
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++) {
string s;
cin>>s;
s=' '+s;
Get_Next(s);
ans=1;
Get_Ans(s);
printf("%lld\n",ans);
}
return 0;
}
|
