[COCI2011-2012#5] POPLOCAVANJE

卡常+分块+奇技淫巧能使AC自动机通过SAM黑题

传送门

首先不考虑空间的AC自动机的做法非常好想对吧，把每个单词都存好，匹配母串，打上标记即可。

但是AC自动机是存不了5000*5000的，但本题讨论中有大佬提供了一个做法，过10~30个字符串求一次答案并重建AC自动机。

但我觉得10~30个字符串非常草率，不如分个块，$\sqrt m$个串优美吧？

那就$\sqrt m$个串求一次答案，空间大概在6e5左右是比较稳的。但有一个坏消息，如果你AC自动机暴力跳fail+暴力打标记+没有优越的AC自动机模板的话，你就会T掉。

现在我来讲解一下一些优化技巧

预处理fail树

首先暴力跳fail是对复杂度影响最大的，我们给每个点附一个值cnt表示如果这个点是单词的结尾的话那个单词的长度，如果是多个就是最长的那个的长度。

我们跳fail实际上是求这个点到fail树根中最大的那个cnt，这个东西可以O(树的大小)处理出来。

那么有一个问题，如果在某点到fail树根的路径上，最大的cnt和某个比他小cnt的区间不同怎么办？（就是选了最大的那个cnt会导致小的cnt的区间计算不到）

不会出现这个情况，因为fail是由长的串指向跟当前串后缀相同的串，一定由长指向短，由母串指向子串，而且在一个点到根的路径上，cnt的最大值是递增的，比最大的cnt小的cnt代表的串一定作为当前串的子串出现过，所以比最大的cnt小的cnt一定曾被作为最大的cnt计算过。

所以我们要把fail树建出来，对其dfs，匹配到一个点时O(1)得到他在到fail树根路径上最大的cnt。

差分打标记

如果你只会fail树而像一个刚学OI的萌新一样暴力打标记的话，那么说明你跟我一样AC自动机学傻了，这个trick是我在只有前面那个优化而T到85分时在神仙@ZUTTER_的代码里找到的，她暴力跳fail但用了这个优化成功的水了过去。

首先我们发现一个被标记打多少次是玄学的，如果你运气不好很可能被卡死，所以打标记的时候要改成对差分数组操作，在区间开头+1，在区间结尾后一位-1。最后做一遍前缀和，如果一个点是0那他一定没有被覆盖。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define re register
using namespace std;
struct node{
    int ch[26],cnt,fail;
}t[600000];
struct edge{
    int next,to;
}w[600001];
char ch[300001],s[5001]; int m;
int n,blo,heap,tail,team[600001];
int bl[5001],o[300001],num,cnt;
int maxn[600001],head[600001],ans;
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
inline void insert(char *s){
    int u=0,l=strlen(s);
    for (re int i=0; i<l; i++){
        int a=s[i]-'a';
        if (!t[u].ch[a]) t[u].ch[a]=++num;
        u=t[u].ch[a];
    }
    t[u].cnt=l;
}
void dfs(int x){
    maxn[x]=max(maxn[x],t[x].cnt);
    for (re int i=head[x]; i; i=w[i].next){
        maxn[w[i].to]=maxn[x]; dfs(w[i].to);
    }
}
inline void build(){
    heap=tail=1; team[heap]=0;
    while (heap<=tail){
        int x=team[heap];
        for (re int i=0; i<26; i++){
            if (t[x].ch[i]){
                team[++tail]=t[x].ch[i];
                if (!x) continue;
                t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
            }
            else t[x].ch[i]=t[t[x].fail].ch[i];
        }
        heap++;
    }
    memset(head,0,sizeof(head)); cnt=0;
    for (re int i=1; i<=num; i++) add(t[i].fail,i);
    dfs(0);
}
inline void change(){
    int u=0;
    for (re int i=1; i<=n; i++){
        int a=ch[i]-'a'; u=t[u].ch[a];
        // for (re int j=u; j; j=t[j].fail)
        // 	if (t[j].cnt) o[i+1]-=1,o[i-t[j].cnt+1]+=1;
        o[i+1]-=1; o[i-maxn[u]+1]+=1;
        // for (re int j=0; j<maxn[u]; j++) o[i-j]=1;
    }
}
int main(){
    scanf("%d",&n);	scanf("%s",ch+1);
    scanf("%d",&m); blo=sqrt(m); bl[0]=1;
    for (re int i=1; i<=m; i++) bl[i]=(i-1)/blo+1;
    for (re int i=1; i<=m; i++){
        scanf("%s",s); insert(s);
        if (bl[i]!=bl[i-1]||i==m){
            build(); change();
            for (re int j=0; j<=num; j++){
                t[j].cnt=t[j].fail=maxn[j]=0;
                for (re int k=0; k<26; k++) t[j].ch[k]=0;
            }
            num=0;// puts("ok");
        }
    }
    // for (re int i=1; i<=n; i++) if (!o[i]) ans++;
    for (re int i=1; i<=n; i++){o[i]+=o[i-1]; if (!o[i]) ans++;}
    printf("%d\n",ans);
    return 0;
}

这份AC自动机代码大概只比正解慢1000ms，目前只有一个AC自动机跑的比我快。
听说调整块的大小能更快