P7114 字符串匹配 - 题解

· · 题解

（纪念我在NOIp2020考场上唯一过掉的题）

题面与思路

先读题：本题要求 S=(AB)^iC 使得 A 中出现奇数次的字符数量 ≤ C 中出现奇数次的字符数量。

很容易想到一种做法：把 (AB) 结合为一个字符串，判断 (AB)^i 是否是 S 的前缀，并用借助预处理统计答案。

具体实现

(AB)^i 判断

这里有一些关于周期的事，想到 KMP算法 中的 fail 数组（或者叫 next 数组）。

此时我们想到一个结论：

字符串A的最短周期 =|A|-fail[A]

于是我们从二开始枚举 i ，只要 S_{|(AB)^i|} 的最短周期是 |AB| 的约数，则 (AB)^i 一定是 S 的前缀。

预处理出 fail 数组即可

答案统计

需要预处理出 S 每个后缀中出现奇数次字符数量即可确定 C 中出现奇数次的字符数量。

统计答案同时更新到每一位时出现奇数次的字符数量 ≤ x(x\in [0,26]) 的 A 的数量。

复杂度分析

首先，对于随机生成的字符串，这种算法时间复杂度为 O(n)

对于形如 a^nC 或 a^n （ a 是单个字符）的字符串，算法的时间复杂度 O( n * \sum\limits_{i=1}^n\frac{1}{i}) = O(n\log n)

复杂度肯定不如题解区里的其他大佬的，但能过CCF

洛谷评测机状态好的时候不开O2也能卡过去，但状态不好时会92~96。开了O2肯定是可以过的。

代码

（请原谅我丑陋的码风）

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
char str[(1<<20)+2]; 
int n,kmp[(1<<20)+2],cir[(1<<20)+2],tms[30],suf[(1<<20)+2],pre[(1<<21)+2],per[27];ll ans;
void deal(){
    char c=getchar();ans=0ll;
    memset(kmp,0,sizeof(kmp));                                  //<初始化>
    memset(cir,0,sizeof(cir));
    memset(tms,0,sizeof(tms));
    memset(suf,0,sizeof(suf));
    memset(pre,0,sizeof(pre));
    memset(per,0,sizeof(per));                                  //</初始化>
    while(c>'z'||c<'a') c=getchar();n=0;int last;               //<读入> 
    while(c<='z'&&c>='a'){str[++n]=c;c=getchar();}              //</读入> 
    for(int i=2;i<=n;i++){last=kmp[i-1];                        //<预处理fail数组>（kmp数组即为 fail数组） 
        while(str[i]!=str[last+1]&&last!=0)last=kmp[last];
        if(str[i]==str[last+1])kmp[i]=last+1;else kmp[i]=0;     //</预处理fail数组>
    }int cnt=0;for(int i=1;i<=26;i++)tms[i]=0;                  //<预处理后缀>
    for(int i=n;i>=1;i--){
        tms[str[i]-'a'+1]++;
        if(tms[str[i]-'a'+1]&1)
            suf[i]=suf[i+1]+1;
        else    suf[i]=suf[i+1]-1;                              //</预处理后缀>
    }for(int i=1;i<=26;i++)tms[i]=0;                            //<预处理前缀>（其实这一段可以画到后面一段里，数组就可以开的小一些） 
    for(int i=1;i<=n;i++){
        tms[str[i]-'a'+1]++;
        if(tms[str[i]-'a'+1]&1)
            pre[i]=pre[i-1]+1;
        else    pre[i]=pre[i-1]-1;
    }                                                           //</预处理前缀>
    for(int i=1;i<n;i++){                                       //处理 
        if(i>=2){                                               //|AB|>=2 此时有解 
            ans+=per[suf[i+1]];                                 //更新答案 
            for(int j=i+i;j<n;j+=i){ 
                if(((i%(j-kmp[j]))==0)&&((j/(j-kmp[j]))>1)){
                    ans+=ll(per[suf[j+1]]);                     //更新周期串答案 
                }else break;
            }
        }
//      printf("*>. seq on %d , cur ans is %lld\n",i,ans);
        for(int j=1;j<pre[i];j++)per[j]=per[j];                 //<更新A中出现j个奇数次数字符时可行的A的数量> 
        for(int j=pre[i];j<=26;j++){
            per[j]=per[j]+1;
        }                                                       //</更新A中出现j个奇数次数字符时可行的A的数量>
    }
//  for(int i=1;i<=n;i++)printf("%d ",pre[i]);printf("\n");//
    printf("%lld\n",ans);
}
int main(){

freopen("string.in","r",stdin);                                 //文件输入输出 
freopen("string.out","w",stdout);                               //文件输入输出

int T;scanf("%d\n",&T);for(;T>0;T--){deal();}return 0;}         //多组数据

大概…………那就这样？