P7114 字符串匹配 题解
x_plus_b
·
·
题解
好像题解区全是KMP，因此提供一种没啥高难算法的做法？
首先发现不需要分别枚举 A,B，可以把 A,B 并成 AB 一起枚举然后再做处理。
对于枚举出来的每个 AB，考虑一个比较暴力的操作：即暴力往后跳 AB 的幂次直到跳到的字符串和 AB 不重合，这样的每一次操作后除了 (AB)^i 之外的剩余字符串都可以作为合法的 C。
首先考虑没有字符出现次数要求的限制怎么做：枚举到的 AB 剖成 A+B 的合法情况共有 len-1
种。用乘法原理乘上枚举出的 C 的数量即可。
看上去这个暴力有点暴力，但实际上判断是否重合可以直接哈希，这样就少了一个 n，剩下的复杂度是O(\sum_{i=1}^{n}\frac{n}{i})，观察到它与 O(nlogn) 是同阶的，所以弱化版的问题就做完了。
接着考虑加上字符出现的频率限制。暴力肯定是过不去的，想办法怎么优化。一种很可行的思路是在刚刚的基础上扣掉所有不合法的情况。
观察到 A 一定为字符串的前缀，而 C 一定为字符串的后缀，所以可以考虑预处理出两个数组 pre,suf 。
$suf_i: str[i-n]$ 中出现奇数次的字母个数
怎么预处理，一个比较可行的办法是开一个大小为 $26$ 的桶，每次加数之后暴力扫，但这题 $n$ 到大约 $10^6$，可能会被卡常。
考虑到，如果一个数 $+1$ 是奇数，那么它原来必定是偶数；如果一个数 $+1$ 是偶数，那么它原来必定是奇数。那么只需要考虑扫到 $i$ 加上的字符加上后是奇数还是偶数。具体的
$pre_i=pre_{i-1}-1$ (如果加上后为偶)
$pre_i=pre_{i-1}+1$ (如果加上后为奇)
$suf$ 同理。
怎么把这个东西加到之前弱化版的做法中？发现如果一个一个枚举 $A$ 和 $C$ 匹配会非常慢。因此我们注意到了一个**只含小写字母**的字符串出现的奇数次字母数量最多只有 $26$ 个，因而可以推出 $pre_i,suf_i \leq 26$。
那么其实可以直接开桶维护了。记 $sum_i$ 为奇数次字母数量为 $i$ 的合法字符串 $A$ 的个数。发现每一次枚举 $AB$ 的长度 $+1$ 时，最多只会出现一个新的合法 $A$ (即为上一次的 $AB$) 所以每一次只需要把上一次出现的新的 $AB$ 的次数塞到桶里即可维护 $sum$。
然后考虑如何计算不合法次数。显然，如果我们不要 $A$ 的奇数字母出现数不超过 $C$ 的奇数字母出现数，那么我们就要计算 $A$ 的奇数字母出现数超过 $C$ 的奇数字母出现数的方案数。
具体的，将计算的这个操作加到之前暴力枚举 $(AB)^i$ 的操作中。记此时 $C$ 为 $str[t-n]$，则所有 $sum_i(i \geq suf_t+1)$ 都是合法的，累加即可。
累加完所有的，在每一次计算贡献时剪去即可。
此时复杂度：$O(26nlogn)$。发现我们取得了 $84$ 分的好成绩。
注意到每一次累加的都是一个桶上的区间，不妨再记一个前缀和来维护这个区间加。并且考虑一些比较好的方式来维护这个前缀和(具体见代码，感性理解一下即可)。
此时复杂度上的 $26$ 常数因子就被拽到了 $n$ 后面，复杂度 $O(n(logn+26))$。
如果实现的和作者一样比较烂，被卡常的话可以考虑给计算哈希值的函数加一个 $\operatorname{inline}$。作者加完后直接快了一倍。
```cpp
#include<bits/stdc++.h>
#define LL long long
#define N 2000005
#define MOD 199485029
#define Base 98
using namespace std;
int T,n;
int sum[127],suf[N],pre[N],SUM[32];
char str[N];
LL ans=0;
LL hashv[N],bpw[N],inv[N];
LL qpow(LL x,LL y)
{
LL res=1;
while(y){
if(y&1) (res*=x)%=MOD;
y>>=1;(x*=x)%=MOD;
}
return res%MOD;
}
void init()
{//inv[i]=1/base^i
for(int i=1;i<=n;i++)
hashv[i]=(hashv[i-1]*Base+str[i])%MOD;
int cnt=0;ans=0;
for(int i=n;i>=1;i--){
sum[str[i]]++;
if(sum[str[i]]&1) cnt++;
else cnt--;
suf[i]=cnt;
}
for(int i='a';i<='z';i++)
sum[i]=0;
cnt=0;
for(int i=1;i<=n;i++){
sum[str[i]]++;
if(sum[str[i]]&1) cnt++;
else cnt--;
pre[i]=cnt;
}
memset(sum,0,sizeof sum);
memset(SUM,0,sizeof SUM);
}
inline LL getnum(int l,int r)
{//(r-l+1)
return ((hashv[r]-(hashv[l-1]*bpw[r-l+1])%MOD)%MOD+MOD)%MOD;
}
inline bool Judge(int l1,int r1,int l2,int r2)
{
return (r1-l1==r2-l2)&&(getnum(l1,r1)==getnum(l2,r2));
}
void solve()
{
scanf("%s",str+1);
n=strlen(str+1);
init();
int len,res;
for(int t=2;t<=n;t++){
for(int i=pre[t-1];i<=26;i++)
SUM[i]++;
len=0,res=0;
for(;len+t<n&&Judge(1,t,len+1,len+t);len+=t)
res+=SUM[26]-SUM[suf[len+t+1]];
len/=t;
ans+=(len*(t-1)-res);
}
printf("%lld\n",ans);
}
int main()
{
bpw[0]=1;n=(1<<20);
for(int i=1;i<=n;i++)
bpw[i]=(bpw[i-1]*Base)%MOD;
inv[n]=qpow(bpw[n],MOD-2);
for(int i=n-1;i>=1;i--)
inv[i]=(inv[i+1]*Base)%MOD;
scanf("%d",&T);
while(T--)
solve();
}
```