2018-team4-modules-AC自动机

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
{
int ch[maxn][26],nodecnt;
    bool danger[maxn];
    inline void insert(char *s){
        int nw = 0;
        for(int i=0,c;s[i] != 0;++i){
            c = s[i] - 'a';
            if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;
            nw = ch[nw][c];
        }danger[nw] = true;
    }
    int q[maxn],l,r,fail[maxn];
    inline void build(){
        l = 0;r = -1;fail[0] = 0;
        for(int c=0;c<26;++c){
            if(ch[0][c]){
                fail[ch[0][c]] = 0;
                q[++r] = ch[0][c];
            }
        }
        while(l <= r){
            int u = q[l++];
            for(int c=0;c<26;++c){
                int t = ch[fail[u]][c];
                if(ch[u][c] == 0) ch[u][c] = t;
                else{
                    fail[ch[u][c]] = t;
                    q[++r] = ch[u][c];
                }
            }
        }
    }
}
}}}

{
int ch[maxn][26],nodecnt;
    bool danger[maxn];
    inline void insert(char *s){
        int nw = 0;
        for(int i=0,c;s[i] != 0;++i){
            c = s[i] - 'a';
            if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;
            nw = ch[nw][c];
        }danger[nw] = true;
    }
    int q[maxn],l,r,fail[maxn];
    inline void build(){
        l = 0;r = -1;fail[0] = 0;
        for(int c=0;c<26;++c){
            if(ch[0][c]){
                fail[ch[0][c]] = 0;
                q[++r] = ch[0][c];
            }
        }
        while(l <= r){
            int u = q[l++];
            for(int c=0;c<26;++c){
                int t = ch[fail[u]][c];
                if(ch[u][c] == 0) ch[u][c] = t;
                else{
                    fail[ch[u][c]] = t;
                    q[++r] = ch[u][c];
                }
            }
        }
    }
}