题解 P7114 【字符串匹配】
囧仙
2020-12-05 23:24:31
## 题目大意
- $T$ 组数据。每组数据给出一个字符串 $S$ ,询问它可以表示成多少种形如 $(AB)^kC$ 的形式,满足 $A$ 中出现**奇数次**的字符个数小于 $C$ 中出现**奇数次**的字符个数。
- 其中 $(AB)^k=\underbrace{AB\cdots AB}_{k \text{个}}$ 。要求 $k\ge 1$ ,且 $A,B,C$ **非空**。
## 题解
> $\rm upd.2020.12.6$ 新增了一个亚 $\log$ 做法,最大的点只需要 $270\text{ms}$ 了。
先想一个 $\mathcal O(tnH(n)+tn|\Sigma|)$ 的做法(其中 $H(n)$ 为调和级数, $H(n)=\sum_{i=1}^n \frac{1}{i}$ 。)
由于题面上给出的形式可以简要拆成两块 $AB,C$ ,所以我们可以枚举其中一部分。
- 观察到, $AB$ 必然是 $S$ 的前缀。我们考虑将 $AB$ 作为整体枚举它的长度 $i$ ,并枚举它的循环节数 $k$ 。
- 显然,我们可以用字符串哈希判断同一个字符串的两个字串是否相等。具体而言,我们设 $T_i=T_{i-1}\times P+S_i$ ,那么满足如下条件时,我们认为两个子串 $S_{a..b},S_{s..t}$ 相等:
$$\frac{T_b-T_{a-1}}{P^{a-1}}=\frac{T_t-T_{s-1}}{P^{s-1}}\Leftrightarrow (T_b-T_{a-1})\times P^{s}=(T_t-T_{s-1})\times P^a$$
枚举完了所有的 $AB$ 以及 $k$ ,我们能够计算出相对应的 $C$ 。现在考虑处理 $AB$ 中的 $A$ 。
- 显然,我们只关心 $A$ 中出现奇数次的字符的个数,而不需要考虑它里面有哪些字符。所以我们能用数组 $N_x$ 存储出现 $x$ 次奇数字符的 $A$ 的个数。由于我们从小到大枚举 $AB$ 的长度 $i$ ,因此第 $i$ 个 $N_x$ 就是在 $i-1$ 的基础上增加了 $S_{1..i-1}$ 这样一种可能的 $A$ 。
- 我们刚刚已经枚举出了所有的 $C$ 。这时统计一下 $C$ 中奇数字符的个数 $t$ ,答案加上 $\sum_{j=1}^k N_j$ 就行了。
如何统计一个字符串中的奇数次字符的数量?
- 事实上,由于字符集 $|\Sigma|=26$ ,所以我们可以用**二进制压缩**的方法,将每个字符看作一位。这样子新增加字符,就相当于**异或**上了它所对应的二进制位(因为偶数次的 $1$ 异或后为 $0$ ,奇数次为 $1$ )。出现奇数次的字符个数就是为 $1$ 的二进制位的个数。
- 此外,由于 $\text{CCF}$ 不能用 $\text{C++11}$ 新增的 $\verb!<bit>! $ ,所以我们要手写 $\verb!pop_count!$ 函数(用于统计二进制位中 $1$ 的个数)。一种简便的做法如下:
- 先计算出 $0\sim 255$ 的每个数字的 $1$ 的个数 $T_i$ 。(显然,有递推式 $T_i=T_{\lfloor i\div 2\rfloor}+(i \operatorname{and} 1)$ )。
- 每个 $32$ 位整数可以用位运算拆成 $4$ 段(具体可以看代码),分别统计再求和即可。复杂度约为 $\mathcal O(4)$ 。
当然,我们还可以用一些优化。
- 显然,枚举的 $C$ 的数量可能比较多(最多 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 个),所以我们用 $N_x$ 的前缀和 $M_x$ 进行优化。复杂度降至 $\mathcal O(tnH(n)+tn|\Sigma|)$ 。
- 输入量较大,建议用 $\verb!getchar!$ 之类。
要记得最大数据 $|S|\le 2^{20}$ 而不是 $10^6$ ,不要开小空间。可能这个做法有点卡常(在机器上极限数据要 $1.5s$ ,洛谷要 $0.7\sim 0.9s$ 左右),注意常数大小。
---
什么?你担心 $\mathcal O(tnH(n))$ 做法不够块,会被卡常?这里提供一个更块的做法。
观察到,上述做法的瓶颈就在于循环节的查询。事实上,我们能够**倍增优化**。
- 假如我们已经发现了循环次数至少为 $k$ 。那么我们只要比较 $S_{1..i\times k}$ 与 $S_{i\times k+1..i\times 2\times k}$ 就能判断循环次数能否达到 $2\times k$ 。
- 对于不是 $2$ 的次幂的循环次数,我们也能如法炮制。先找到最大的 $k_m=2^s$ 使得循环节长度不小于 $k_m$ 。从 $k_m$ 枚举,每次折半,判断接下来 $i\times k$ 个字符与字符串开头的 $i\times k$ 的字符相同(使用字符串哈希)。这样复杂度就更低了。
- 搜寻长度为 $i$ 的 $AB$ 出现了多少次,从 $\mathcal O(\frac{n}{i})$ 优化到了 $\mathcal O(\log\frac{n}{i})$ 。
此外,前缀和部分可以用树状数组优化。从单次 $\mathcal O(|\Sigma|)$ 优化到 $\mathcal O(\log |\Sigma|)$ 。
复杂度比较玄学,大概长这样:
$$t\times \left(\sum_{i=1}^n \log\left\lfloor\frac{n}{i}\right\rfloor+n\log|\Sigma|\right)$$
显然,它是可以通过极限数据的。
## 参考代码
```cpp
//第一版
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
i64 qread(){
i64 r=0,w=1; char c;
while(!isdigit(c=getchar())) w=(c=='-'?-1:1); r=c-'0';
while( isdigit(c=getchar())) r=r*10+c-'0';
return r*w;
}
const int MAXN =(1<<20)+3,P=13331;
u64 H[MAXN],T[MAXN],N[30],ans; int C[256+3],W[MAXN],n,m=MAXN-1,t,c; char S[MAXN];
int ppc(int x){ //pop_count
return C[(x>>24)&255]+C[(x>>16)&255]+C[(x>>8)&255]+C[x&255];
}
int main(){
up(0,255,i) C[i]=C[i>>1]+(i&1); T[0]=1; up(1,m,i) T[i]=T[i-1]*P;
dn(qread(),1,TTT){
while(!isalpha(c=getchar())); S[++n]=c;
while( isalpha(c=getchar())) S[++n]=c;
up(1,n,i) W[i]=W[i-1]^(1<<(S[i]-'a')),H[i]=H[i-1]*P+S[i];
t=ppc(W[n]);
up(1,n-1,i){
int w=W[i],_w=W[n]^W[i],a=ppc(_w),b=t;
if(i>1) for(int j=1;i*j<n;++j){
if(H[i*j]-H[i*j-i]==H[i]*T[i*j-i]) ans=ans+N[(j&1)?a:b];
else break;
}
up(ppc(w),26,j) ++N[j];
}
printf("%llu\n",ans),ans=n=0;
memset(N,0,sizeof(N));
}
return 0;
}
//优化版
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
i64 qread(){
i64 r=0,w=1; char c;
while(!isdigit(c=getchar())) w=(c=='-'?-1:1); r=c-'0';
while( isdigit(c=getchar())) r=r*10+c-'0';
return r*w;
}
const int MAXN =(1<<20)+3,P=13331,MAXM=26+3;
u64 H[MAXN],T[MAXN],ans; int C[256+3],W[MAXN],n,m=MAXN-1,t,c; char S[MAXN];
int ppc(int x){ //pop_count
return C[(x>>24)&255]+C[(x>>16)&255]+C[(x>>8)&255]+C[x&255];
}
u64 O[MAXM];
void add(int x){++x; while(x<MAXM) ++O[x],x+=x&-x;}
int qry(int x){++x; int r=0; while(x) r+=O[x],x-=x&-x; return r;}
int main(){
up(0,255,i) C[i]=C[i>>1]+(i&1); T[0]=1; up(1,m,i) T[i]=T[i-1]*P;
dn(qread(),1,TTT){
while(!isalpha(c=getchar())); S[++n]=c;
while( isalpha(c=getchar())) S[++n]=c;
up(1,n,i) W[i]=W[i-1]^(1<<(S[i]-'a')),H[i]=H[i-1]*P+S[i];
t=ppc(W[n]);
up(1,n-1,i){
int w=W[i],_w=W[n]^W[i],a=ppc(_w),b=t,k,p;
for(k=1; ;k<<=1) if(i*k*2>=n||H[i*2*k]-H[i*k]!=H[i*k]*T[i*k]) break;
for(p=k;k;k>>=1) if(i*(p+k)<n&&H[i*(p+k)]-H[i*p]==H[i*k]*T[i*p]) p+=k;
ans=ans+(p+1)/2*qry(a)+p/2*qry(b),add(ppc(w));
}
printf("%llu\n",ans),ans=n=0;
memset(O,0,sizeof(O));
}
return 0;
}
```