题解 P4595 【[COCI2011-2012#5] POPLOCAVANJE】

· · 题解

因为是最优解就来写题解了（滑稽）

从数据大小上分析，这道题的 n 的大小比较大，但是图案的大小和图案个数 m 都比较小，较普遍的算法是使用AC自动机进行字符匹配，但是这里我们使用哈希，在加上优化后不仅空间比AC自动机小很多，而且在普遍的测试点中时间非常快，所有测试点时间之和只有657ms。

先考虑比较朴素的匹配，即将 m 个小字符串进行哈希，再在大字符串上 O(n) 进行匹配，然后通过差分来实现对能铺的位置的覆盖。

但是显然这样的时间复杂度是 O(n\times m) ，所以我们要对算法进行优化。

首先一个较明显的思路是对字符串的开头第一个字母进行分类，先将m个哈希值预处理出来，再按照首字母分别装到不同的数组中，在每次询问的时候只要询问需要的首字母的数组即可，那么这样的时间复杂度度就能减少26倍。

这样就已经是第二优解了，但是这并不是最快的，我们还可以再每个大字符串的字符匹配时，从长度最大的字符串开始匹配，这样当我们匹配成功时，剩下的部分就没有必要在匹配了。

于是一个简单的哈希加差分加剪枝就能飞快地A掉这道黑题。 ٩(๑❛ᴗ❛๑)۶

下面是我自己的代码。

ps:我使用的是对最后一个字符进行分类，这样能防止被卡，使代码更快。

#include<bits/stdc++.h>
#define un unsigned long long
using namespace std;
const int N=3e5+5;
struct z{
    int Len;
    un Has;
} g[30][5005];//将哈希值与长度装在结构体中方便排序和调用
int n,m,Len,cnt[30],L[N];
un f[N],num[N],p;
char a[N],s[5005];
bool cmp(z a,z b){
    return a.Len>b.Len;
}
int main(){
    scanf("%d%s",&n,&a);
    num[0]=1;
    for(int i=0;i<n;i++)f[i]=f[i-1]*233+a[i],num[i+1]=num[i]*233;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",&s);
        Len=strlen(s);
        int mb=s[Len-1]-'a';//按照尾字母分类
        p=0;
        for(int j=0;j<Len;j++)p=p*233+s[j];
        g[mb][++cnt[mb]]=(z){Len,p};
    }
    for(int i=0;i<26;i++)sort(g[i]+1,g[i]+cnt[i]+1,cmp);
    for(int i=0;i<n;i++){
        int mb=a[i]-'a';//按照尾字母进行查询
        for(int j=1;j<=cnt[mb];j++){
            Len=g[mb][j].Len;
            if(i<Len-1)continue;
            if(f[i]-f[i-Len]*num[Len]==g[mb][j].Has){
                L[i-Len+1]++,L[i+1]--;//对覆盖区域进行差分
                break;//剩下的都是比当前字符串短的，就算匹配成功对答案也没有贡献，可以直接break
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(i>0)L[i]+=L[i-1];
        if(L[i]==0)ans++;
    }
    cout<<ans;
}