2023年7月20日发(作者：)

「NOIP2020提⾼」字符串匹配题解Statement⼩ C 学习完了字符串匹配的相关内容，现在他正在做⼀道习题。对于⼀个字符串 S，题⽬要求他找到 S 的所有具有下列形式的拆分⽅案数：S=ABC，S=ABABC，S=ABAB…ABC，其中 A，B，C 均是⾮空字符串，且 A 中出现奇数次的字符数量不超过 C 中出现奇数次的字符数量。并递归地定义 A1=A，An=An−1A（n≥2 且为正整数）。例如 A=abb，则 A3=abbabbabb。则⼩ C 的习题是求 S=(AB)iC 的⽅案数，其中 F(A)≤F(C)，F(S) 表⽰字符串 S 中出现奇数次的字符的数量。两种⽅案不同当且仅当拆分出的 A、B、C 中有⾄少⼀个字符串不同。⼩ C 并不会做这道题，只好向你求助，请你帮帮他。Input本题有多组数据，输⼊⽂件第⼀⾏⼀个正整数 TT 表⽰数据组数。每组数据仅⼀⾏⼀个字符串 SS，意义见题⽬描述。SS 仅由英⽂⼩写字母构成。Output对于每组数据输出⼀⾏⼀个整数表⽰答案。ExampleInput:3 nnrnnr zzzaab mmlmmloOutput:8 9 16Solve 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) 的，⼤致长这个样⼦：Processing math: 100%for(int i=3;i<=n;++i){ vectorg; int pos=i-1; while(pos){ if((i-1)%(i-1-kmp[pos])==0) _back(kmp[pos]); pos=kmp[pos]; } for(int j=0;j<(int)();++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++; } }}我们可以⼀层层 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)，我们拿到了 48ptsOpt3这个思路来⾃我们可以尝试向 O(nlogn) 前进。考虑我们为什么需要把 (AB)x 的所有位置都扫⼀遍来枚举 A是因为我们不清楚⼩于等于 suf[i] 的 pre[j] 有哪些，同时他们的“权重”（tot）也不确定我们设⼀个数组 sum[i] 表⽰ pre ⼩于等于 i 的数量，那么，这样就可以 O(26n) 求到：for(int i=1;i=2){//|AB|>=2 才贡献答案 ans+=sum[suf[i+1]]; for(int j=i+i;j1)//是循环节且不是本⾝ ans+=sum[suf[j+1]]; else break; } for(int j=pre[i];j<=26;++j) sum[j]++;}这⾥，sum 的作⽤和前⾯的 tot*(pre[j]<=suf[i])差不多（感觉⾃⼰讲的不是很清楚，sum 事实上是⼀个动态的过程）这样的复杂度是多少？其实跑不满， n 是 1e6 左右，能过（反正 ccf 过了。Code#include#define int long longusing namespace std;const int N = 2e6+5;void file(){ freopen("","r",stdin); freopen("","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;O(n∗i∑n1=1i)=O(nlogn) 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=2){ ans+=sum[suf[i+1]]; for(int j=i+i;j1) ans+=sum[suf[j+1]]; else break; } for(int j=pre[i];j<=26;++j) sum[j]++; } printf("%lldn",ans); } return 0;

}Solve2⽅法：EXKMPO(nlogn) 我不满意！我要 O(n) 算法！显然，我们 Slove1 的思路到达了⼀定的瓶颈，我们考虑采⽤另⼀种思路由于这位⼤佬 tql，⽽且写得⾮常明⽩，作者⾃认讲得没这个清楚所以⼤家直接去 % 这位⼤佬就可以啦