题解 P7114 【字符串匹配】

囧仙

2020-12-05 23:24:31

Solution

## 题目大意 - $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; } ```