囧仙 的博客

囧仙 的博客

题解 P7114 【字符串匹配】

posted on 2020-12-05 23:24:31 | under 题解 |

题目大意

  • $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)$$

显然,它是可以通过极限数据的。

参考代码

//第一版
#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;
}