P9453 [ZSHOI-R1] 有效打击 题解
ckain
·
·
题解
首先我们将 B 做成最小形式．
设 B 被分为若干段相同的字符，将它们长度统一除以它们的 \gcd，得到串 B_{min}． 由于相似的传递性，有与 B 相似等价于与 B_{min} 相似．
与 B_{min} 相似，必须满足其是 B_{min} 放大整数倍的结果．
证明：
考虑反证．设 X 是与 B_{min} 相似的串，有
X=\frac{p}{q}B_{min}\;(\gcd(p,q)=1)
---
若 $B_{min}$ 的长度是 $1$，求解答案是容易的．
若 $B_{min}$ 的长度不是 $1$，枚举 $A$ 中可能作为 $B_{min}$ 相似串的右端点．可以发现，当固定右端点时，$B_{min}$ 被放大的倍数是确定的．
考虑字符串哈希．我们先预处理出每种放大倍数下，$B$ 串的哈希值．然后对 $A$ 串做区间哈希即可完成对每个右端点 $O(1)$ 检查．
总时间复杂度 $O(n\log n)$．瓶颈在求 $\gcd$．
code：
```cpp
#include<bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define int long long
using namespace std;
inline int rd(void){
int s=0, f=1; char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=0; c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-'0'; c=getchar();}
return f? s:-s;
}
const int N=5e6+5, P=390831, Mod=1e9+7;
int n, m, a[N], b[N];
int pw[N], spw[N], hsha[N], hshb[N];
int len[N], c[N], tot, s;
int now[N];
void init(){
pw[0]=spw[0]=1;
for(int i=1; i<=n; i++) pw[i]=pw[i-1]*P%Mod, spw[i]=(spw[i-1]+pw[i])%Mod;
for(int i=1; i<=n; i++) hsha[i]=(hsha[i-1]*P%Mod+a[i])%Mod;
for(int i=1; i<=m; i++){
int j=i;
while(j<m && b[j+1]==b[i]) j++;
len[++tot]=j-i+1;
c[tot]=b[i];
i=j;
}
int Gcd=len[1];
for(int i=2; i<=tot; i++) Gcd=__gcd(Gcd, len[i]);
for(int i=1; i<=tot; i++) len[i]/=Gcd, s+=len[i];
for(int i=1; s*i<=n; i++){
for(int j=1; j<=tot; j++){
now[j]=(now[j-1]*pw[len[j]*i]%Mod+spw[len[j]*i-1]*c[j]%Mod)%Mod;
}
hshb[i]=now[tot];
}
}
int que(int l, int r){
return (hsha[r]-hsha[l-1]*pw[r-l+1]%Mod+Mod)%Mod;
}
void solve(){
int ans=0;
if(tot==1)
for(int i=1, prelas=-1; i<=n; i++){
if(a[i]!=c[tot]) prelas=-1;
else if(prelas==-1) prelas=i;
if(a[i]==c[tot]) ans+=(i-prelas+1);
}
else
for(int i=1, prelas=-1; i<=n; i++){
if(a[i]!=c[tot]) prelas=-1;
else if(prelas==-1) prelas=i;
if(a[i]==c[tot]){
if((i-prelas+1)%len[tot]==0){
int k=(i-prelas+1)/len[tot];
if(que(i-k*s+1, i)==hshb[k]) ans++;
}
}
}
printf("%lld\n", ans);
}
signed main(){
n=rd(), m=rd();
for(int i=1; i<=n; i++) a[i]=rd();
for(int i=1; i<=m; i++) b[i]=rd();
init();
solve();
return 0;
}
```