WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
AC自动机模版
AC自动机模版
namespace ACMachine{
    const int MAXN=1e7+50;
    const int KIND=10;
    struct Tree{
        int siz;
        int ch[KIND], fail;
    };
    Tree tree[MAXN];
    int nume, root;

    inline int newNode(){
        int x=++nume;
        for (int i=0; i<KIND; i++) tree[x].ch[i]=0;
        tree[x].siz=tree[x].fail=0;
        return x;
    }

    inline void init(){
        nume=0;
        root=newNode();
    }

    int insert(int x, char str[]){
        int c, len=strlen(str);
        for (int i=0; i<len; i++){
            c=str[i]-'0';
            if (tree[x].ch[c]==0) tree[x].ch[c]=newNode();
            x=tree[x].ch[c];
        }
        tree[x].siz++;
        return x;
    }

    queue<int> que;
    void build(int x){
        while(!que.empty()) que.pop(); que.push(x);
        while(!que.empty()){
            x=que.front(); que.pop();
            for (int c=0; c<KIND; c++){
                int now=tree[x].ch[c];
                if (now){
                    if (x==root) tree[now].fail=root; else{
                        int p=tree[x].fail;
                        while(p){
                            if (tree[p].ch[c]){
                                tree[now].fail=tree[p].ch[c];
                                break;
                            }
                            p=tree[p].fail;
                        }
                        if (!p) tree[now].fail=root;
                    }
                    que.push(now);
                }
            }
        }
    }

    int query(int x, char str[]){
        int ret=0, len=strlen(str);
        for (int i=0; i<len; i++){
            int c=str[i]-'0';
            while(!tree[x].ch[c] && x!=root) x=tree[x].fail;
            x=tree[x].ch[c];
            if (x==0) x=root;

            int now=x;
            while(now!=root){
                if (tree[now].siz>=0){
                    ret+=tree[x].siz;
                    tree[x].siz=-1;
                }else break;
                now=tree[now].fail;
            }
        }
        return ret;
    }
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

AC自动机模版
namespace ACMachine{ const int MAXN=1e7+50; const int KIND=10; struct Tree{ int siz; int ch[KIND], fail; }; Tree tree[MAXN]; int nume,…
扫描二维码继续阅读
2018-10-11
<--! http2https -->