题目大意
PCY 学生物学累了。突然看到地上有一本笔记本。
上面写着“isdashagaydashisorisdashnot…”之类的字眼，独具慧眼的他发现这些字符串中有着大秘密！类似“isdash”这样的前缀在字符串中出现的次数不止一次！他觉得这其中一定有蹊跷，于是开始一个一个数前缀出现的次数。
虽然他早已经从逐字符匹配转换到了多行同时匹配模式，但是这小小的练习本上几十万个字符还是让他措手不及。你能帮助他吗？他想知道所有长度为偶数的前缀在整个字符串出现的次数和。
题目分析
若一个串失配，必返回其$fail$指针所指位置，故$i$处必定包含$fail[i]$所包含的前缀，从左往右递推一遍即可。
注意使用AC自动机版的失配指针。
此题还可以用后缀自动机，请自行食用。
代码
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
| #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;
}
const int maxn=200005;
int Next[maxn];
LL f[maxn],ans=0;
void Get_Next(string s) {
s=' '+s;
for(int i=2; i<=s.length(); i++) {
int p=Next[i-1];
while(p&&s[p+1]!=s[i])p=Next[p];
Next[i]=(s[p+1]==s[i])?p+1:0;
}
}
int main() {
ios::sync_with_stdio(false);
string s;
cin>>s;
Get_Next(s);
for(int i=1; i<=s.length(); i++) {
if((i&1)==0)f[i]=1;
f[i]+=f[Next[i]];
ans+=f[i];
}
printf("%lld\n",ans);
return 0;
}
|
