struct AhoCorasickAutomaton
{
    static const int alp=26;

    static int to_idx(char ch)
    {
        return ch-'a'+1;
    }

    struct Trie
    {
        static const int __=1000005;
        struct node
        {
            int nex[alp+1],last,num;
            bool add[alp+1];
            void clear()
            {
                num=last=0;
                mem(nex,0);
                mem(add,false);
            }
        }t[__];

        Trie() {clear();}

        node& operator[](int x){return t[x];}

        int idx;

        void insert(char s[],int len)
        {
            int x=0;
            for(int i=1;i<=len;++i)
            {
                int k=to_idx(s[i]);
                if(!t[x].nex[k])
                {
                    t[x].nex[k]=++idx;
                    t[idx].clear();
                }
                x=t[x].nex[k];
            }
            //标记结尾
        }

        void clear(){idx=0;t[0].clear();}
    }t;

    AhoCorasickAutomaton() {clear();}

#define nex(x) t[x].nex[i]
#define fail(x) t[x].nex[0]

    void get_fail()
    {
        queue<int>Q;Q.push(0);
        while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            for(int i=1;i<=alp;++i)
                if(nex(x))
                {
                    Q.push(nex(x));
//                    for(int y=x;y;y=fail(y))
//                        if(nex(fail(y)))
//                        {
//                            fail(nex(x))=nex(fail(y));
//                            break;
//                        }
                    if(x)fail(nex(x))=nex(fail(x));
                }
                else
                {
                    nex(x)=nex(fail(x));
                    t[x].add[i]=true;
                }
            if(t[fail(x)].num)t[x].last=fail(x);
            else t[x].last=t[fail(x)].last;

        }
    }

    int ac(char s[],int len)
    {
        int ans=0;
        for(int i=1,x=0;i<=len;++i)
        {
            int k=to_idx(s[i]);
//            while(x && !t[x].nex[k])x=fail(x);
            x=t[x].nex[k];
            for(int y=x;y;y=t[y].last)
                ;//统计答案
        }
        return ans;
    }

    void debug()
    {
        for(int i=0;i<=t.idx;++i)
        {
            pf("t[%d]: fail:%d last:%d\n",i,fail(i),t[i].last);
            for(int j=1;j<=26;++j)
                if(t[i].nex[j])
                    printf("%d(%c) ",t[i].nex[j],j-1+'a');
            puts("\n");
        }
    }

    void clear(){t.clear();}
}aca;