BZOJ 3172 單詞（AC自動機）

題意

https://www.lydsy.com/JudgeOnline/problem.php?id=3172

思路

\(\text{AC}\)自動機模闆題，稍微點一下 \(\text{AC}\)自動機。

\(\text{AC}\)自動機說白了就是在 \(\text{Trie}\) 樹上跑 \(\text{KMP}\)。

它通過廣搜來預處理 \(fail\) 指針。一個從節點 \(a\) 到節點 \(b\) 的 \(fail\) 指針，代表除 \(a\) 本身外，最長能在自動機上找到的字尾 。如上圖從字母e指向字母e的指針。同時處理出在自動機上的每一個節點，之後再向自動機内輸入哪個字母，它會跑到哪裡（省去了跳 \(fail\) 指針的過程），直接用 \(Trie\) 樹的 \(ch\) 數組表示（将 \(Trie\) 樹變成了 \(Trie\) 圖），在 \(\text{KMP}\) 的部分題目中已經展現出了這種思想。

其實整個算法中最重要的還是 \(fail\) 指針，\(fail\) 指針代表字尾相等。不難發現，\(fail\) 指針構成了一棵樹，每跳一次 \(fail\) 指針，在 \(Trie\) 樹上的深度至少減 \(1\) 。\(fail\) 的樹形結構在解題中尤為關鍵。

還有關于“自動機”一詞，我想可以這樣了解，先将模式串構成自動機，文本串一個字元一個字元的輸入這個機器，\(ch\) 數組表示比對指針的跳動，并用 \(fail\) 指針将影響傳遞給所有需要影響的位置。

這題是\(\text{AC}\)自動機最基礎的運用之一。首先将模式串（即文章中的單詞）建立自動機，然後将文章輸入自動機。由于要傳遞影響，暴力的寫法是所有比對指針到的位置都應該跳 \(fail\) 指針直到根，中途節點答案加一，但是這樣複雜度過不去。利用 \(fail\) 的樹形結構，直接在比對指針到的位置加 \(1\) ，最後一遍差分上來即可。

代碼

#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
typedef long long LL;
using namespace std;
const int N=1e6+5;
template<const int maxn,const int maxm>struct Linked_list
{
    int head[maxn],to[maxm],nxt[maxm],tot;
    Linked_list(){clear();}
    void clear(){memset(head,-1,sizeof(head));tot=0;}
    void add(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}
    #define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])
};
Linked_list<N,N>G;
int ch[N][27],f[N],occ[N];
char T[N];
char P[205][N];
int rt,tot,n,q;

void build(){rt=tot=0;}
void create(int &k)
{
    if(!k)
    {
        k=++tot;
        FOR(i,0,26)ch[k][i]=0;
        occ[k]=0;
    }
}
void insert(int &k,char *str,int len)
{
    create(k);
    int now=k;
    FOR(i,0,len-1)
    {
        create(ch[now][str[i]-'a']);
        now=ch[now][str[i]-'a'];
    }
}
void getfail()
{
    queue<int>Q;
    while(!Q.empty())Q.pop();
    f[rt]=rt;
    FOR(i,0,26)
    {
        if(ch[rt][i])f[ch[rt][i]]=rt,Q.push(ch[rt][i]);
        else ch[rt][i]=rt;
    }
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        FOR(i,0,26)
        {
            if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],Q.push(ch[u][i]);
            else ch[u][i]=ch[f[u]][i];
        }
    }
}
void dfs_fail(int u)
{
    EOR(i,G,u)
    {
        int v=G.to[i];
        dfs_fail(v);
        occ[u]+=occ[v];
    }
}
void KMP()
{
    G.clear();
    FOR(i,1,tot)if(f[i]!=i)G.add(f[i],i);
    int now=rt;
    FOR(i,0,n-1)
    {
        now=ch[now][T[i]-'a'];
        occ[now]++;
    }
    dfs_fail(rt);
}
int query(int k,char *str,int len)
{
    int now=k;
    FOR(i,0,len-1)now=ch[now][str[i]-'a'];
    return occ[now];
}

int main()
{
    build();
    scanf("%d",&q);
    char *h=T;
    FOR(i,1,q)
    {
        scanf("%s",P[i]);
        insert(rt,P[i],strlen(P[i]));
        FOR(j,0,strlen(P[i])-1)*h=P[i][j],h++,n++;
        *h='{',h++,n++;
    }
    *h='\0';
    
    getfail();
    KMP();
    FOR(i,1,q)printf("%d\n",query(rt,P[i],strlen(P[i])));
    return 0;
}                

轉載于:https://www.cnblogs.com/Paulliant/p/10205372.html