「NOIP2020提⾼」字符串匹配题解
Statement
⼩ C 学习完了字符串匹配的相关内容，现在他正在做⼀道习题。
对于⼀个字符串 S，题⽬要求他到 S 的所有具有下列形式的拆分⽅案数：
S=ABC，S=ABABC，S=ABAB…ABC，其中 A，B，C 均是⾮空字符串，且 A 中出现奇数次的字符数量不超过 C 中出现奇数次的字符数量。
并递归地定义 A1=A，A n=A n−1A（n≥2 且为正整数）。例如 A=abb，则 A3=abbabbabb。
则⼩ C 的习题是求 S=(AB)i C 的⽅案数，其中 F(A)≤F(C)，F(S) 表⽰字符串 S 中出现奇数次的字符的数量。两种⽅案不同当且仅当拆分出的 A、B、C 中有⾄少⼀个字符串不同。⼩ C 并不会做这道题，只好向你求助，请你帮帮他。
Input
本题有多组数据，输⼊⽂件第⼀⾏⼀个正整数 T T 表⽰数据组数。
每组数据仅⼀⾏⼀个字符串 S S，意义见题⽬描述。S S 仅由英⽂⼩写字母构成。
Output
对于每组数据输出⼀⾏⼀个整数表⽰答案。
Example
Input:
3 nnrnnr zzzaab mmlmmlo
Output:
8 9 16
Solve 1
⽅法：KMP
我们⾸先简要概括题⽬：
给定字符串 S，问有多少不同的⾮空字符串 A，B，C 满⾜ ABC 且 A 中出现奇数次的字符数不多于 C。
第⼀眼发现：循环节
我们知道⼀个 KMP 有⼀个优秀的性质，或者叫做引理：（这⾥ n=|S| ）
若n，则n−kmp[n] 是最⼩循环节长度
若n%(n−kmp[kmp[n]])==0 ，则n−kmp[kmp[n]] 是次⼩循环节长度
以此类推
（这个不懂的建议看看蓝书或者上⽹）
那我们显然有⼀个暴⼒的想法：（字符串下标从 1开始，S[i,j]={s[i],s[i+1]…s[j]}）
枚举i=3…n−1表⽰C=S[i,n−1]
求出S[1,i−1]即 (AB)x的所有循环节
对于每⼀个循环节，枚举A具体是什么，根据题⽬条件统计答案
注意 A,B,C 皆不能为空串
显然，这个是 O(n4)的，⼤致长这个样⼦：
空字符串是什么for(int i=3;i<=n;++i){
vector<int>g;
int pos=i-1;
while(pos){
if((i-1)%(i-1-kmp[pos])==0)
g.push_back(kmp[pos]);
pos=kmp[pos];
}
for(int j=0;j<(int)g.size();++j){
int len=i-1-g[j];//|AB| = len
for(int k=1;k<=len;++k){//枚举 A = S[1,k]
for(int h=1;h<=k;++h)//统计前 k 个中，出现次数为奇数字符个数，假设为 cnt
if(cnt<=C 中出现次数为奇数字符数) ans++;
}
Processing math: 100%
}
}
我们可以⼀层层 for 优化
Opt1
发现每次判断是否满⾜条件时（A 中出现奇数次的字符数不多于 C）
其实是在判断⼀个 f(prefix) ，和⼀个 f(suffix)
显然我们可以 O(n) 预处理：
void prework(){
len=strlen(s);
memset(cnt,0,sizeof cnt);
for(int i=1,tot=0;i<=len;++i)
if((++cnt[s[i]-'a'])&1)pre[i]=++tot;
else pre[i]=--tot;
memset(cnt,0,sizeof cnt);
for(int i=len,tot=0;i;--i)
if((++cnt[s[i]-'a'])&1)suf[i]=++tot;
else suf[i]=--tot;
}
这样，最⾥⾯的 for 简化成 O(1)：
if(pre[k]<=suf[i])ans++;
Opt2
观察，发现其实对于多个不同的循环节，都有可能枚举同样的 k 进⾏贡献，⽽且，对于⼀个更长的循环节，它应该包含⽐他短的循环节的取值集合。也就是说，设循环节 a,b ，其中 |a|<|b|，那么如果 ∃k<|a|,pre[k]<=suf[i] 则这个 k 在扫描 b 的时候也会被更新。
（上⾯的话可能有点绕，但其实很显然）
我们可以写出如下的代码：
for(int i=3;i<=len;++i){
int pos=i-1;
while(pos){
if((i-1)%(i-1-kmp[pos])==0)
vis[i-1-kmp[pos]]=1;
pos=kmp[pos];
}
for(int j=i-1,tot=0;j;--j){
ans+=tot*(pre[j]<=suf[i]);
tot+=vis[j],vis[j]=0;
}
}
我们⽤⼀个 vis 数组标明循环节的位置，然后每经过⼀个被标记的点，tot++，代表有 tot 个循环节可以⽤当前长度为 j 的 A 进⾏更新。
注意要逆序扫描。
这样，经过上⾯两个优化，时间复杂度来到了 O(n2)，我们拿到了 48pts
Opt3
这个思路来⾃
我们可以尝试向 O(n log n)前进。
考虑我们为什么需要把 (AB)x的所有位置都扫⼀遍来枚举 A
是因为我们不清楚⼩于等于 suf[i] 的 pre[j] 有哪些，同时他们的“权重”（tot）也不确定
我们设⼀个数组 sum[i]表⽰ pre⼩于等于 i的数量，那么，这样就可以 O(26n)求到：
for(int i=1;i<len;++i)
for(int j=pre[i];j<=26;++j)//多了 pre[i] 这个点可以贡献
sum[j]++;
作者没有想到什么好办法，只能枚举循环节了。
在尝试写代码后发现，我们如果还是枚举 C 的话，不是很好写。
我们考虑把 (AB) 结合为⼀个字符串，判断 (AB)i 是否是 S 的前缀，并⽤借助 sum 统计答案。
也就是说，我们第⼀层循环枚举 (AB)
如何判断是否是前缀？
设 j=(AB)x ，如果 j−kmp[j] ，它的最⼩循环节是 |AB| 的约数，那 j 就是 S 的前缀这个可以画画图，发现是显然的。
for(int i=1;i<len;++i){
if(i>=2){//|AB|>=2 才贡献答案
ans+=sum[suf[i+1]];
for(int j=i+i;j<len;j+=i)
if(!(i%(j-kmp[j]))&&j/(j-kmp[j])>1)//是循环节且不是本⾝
ans+=sum[suf[j+1]];
else break;
}
for(int j=pre[i];j<=26;++j)
sum[j]++;
}
这⾥，sum 的作⽤和前⾯的 tot*(pre[j]<=suf[i])差不多
（感觉⾃⼰讲的不是很清楚，sum 事实上是⼀个动态的过程）
这样的复杂度是多少？
O(n∗
n
∑
i=1
1
i)=O(n log n)
其实跑不满， n 是 1e6 左右，能过（反正 ccf 过了。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
void file(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
}
int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
char s[N];
int kmp[N],cnt[30];
int pre[N],suf[N],sum[N];
int T,len;
void prework(){
memset(cnt,0,sizeof cnt);
for(int i=1,tot=0;i<=len;++i)
if((++cnt[s[i]-'a'])&1)pre[i]=++tot;
else pre[i]=--tot;
memset(cnt,0,sizeof cnt);
for(int i=len,tot=0;i;--i)
if((++cnt[s[i]-'a'])&1)suf[i]=++tot;
else suf[i]=--tot;
}
void KMP(){
memset(kmp,0,sizeof kmp);
for(int i=2,j=0;i<=len;++i){
while(s[i]!=s[j+1]&&j)j=kmp[j];
if(s[i]==s[j+1])j++;
kmp[i]=j;
}
}
signed main(){
T=read();
while(T--){
char c=getchar();
while(c>'z'||c<'a')c=getchar();len=0;
while(c<='z'&&c>='a')s[++len]=c,c=getchar();
int ans=0;
prework();KMP();
memset(sum,0,sizeof(sum));
for(int i=1;i<len;++i){
if(i>=2){
ans+=sum[suf[i+1]];
for(int j=i+i;j<len;j+=i)
if(!(i%(j-kmp[j]))&&j/(j-kmp[j])>1)
ans+=sum[suf[j+1]];
else break;
}
for(int j=pre[i];j<=26;++j)
sum[j]++;
}
printf("%lld\n",ans);
}
return 0;
}
Solve2
⽅法：EXKMP
O(n log n) 我不满意！我要 O(n) 算法！
显然，我们 Slove1 的思路到达了⼀定的瓶颈，我们考虑采⽤另⼀种思路由于这位⼤佬 tql，⽽且写得⾮常明⽩，作者⾃认讲得没这个清楚
所以⼤家直接去 % 这位⼤佬就可以啦

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。