题目大意
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; }
|