AC自动机

要先赋值 \(Sigma\) 为字符集大小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
namespace ACautomaton
{
    static const int Sigma=52;
    int ch[MAX][30],d[MAX],fail[MAX],tot;
    char s[MAX]; int len;
    queue<int> q;

    inline int getid(char c) {if(c>='a'&&c<='z') return c-'a'; return c-'A'+26;}
    void insert(int id)
    {
        int now=0; len=strlen(s+1);
        for(int i=1;i<=len;++i)
        {
            int to=getid(s[i]);
            if(!ch[now][to]) ch[now][to]=++tot;
            now=ch[now][to];
        }
        d[id]=now;
    }
    inline void build()
    {
        int now=0;
        for(int i=0;i<=Sigma;++i) if(ch[now][i]) q.emplace(ch[now][i]);
        while(!q.empty())
        {
            now=q.front(); q.pop();
            G[fail[now]].eb(now);
            for(int i=0;i<=Sigma;++i)
                if(ch[now][i]) fail[ch[now][i]]=ch[fail[now]][i],q.emplace(ch[now][i]);
                else ch[now][i]=ch[fail[now]][i];
        }
    }
}