호남대학 교 ACM 프로 그래 밍 신 생 컵 대회 F string (AC 자동 동기)

https://ac.nowcoder.com/acm/problem/14612
제목: 간단 합 니 다. 문자열 을 추가 한 다음 에 특정한 문자열 에 몇 번 나 왔 는 지 알 아 보 는 것 입 니 다. 몇 개가 아 닙 니 다.
방법: 이 문 제 는 보통 KMP 를 사용 하면 안 됩 니 다. 다른 KMP 는 잘 모 르 겠 습 니 다. 먼저 생각 나 는 것 은 바로 AC 자동 동기 입 니 다. 그러나 우리 가 배 운 AC 자동 동 기 는 중간 에 문자열 을 넣 는 기능 이 없습니다. 제 가 먼저 생각 나 는 것 은 폭력 건설 Trie 가 아니 라 직접적 으로 T 를 만 들 었 다 는 것 입 니 다. 그 후에 큰 사람의 코드 를 보 았 습 니 다. 그 는 2 진법 으로 분 리 된 Trie 입 니 다.나 는 나 무 를 세 우 는 복잡 도가 많 지 않 을 것 이 라 고 생각한다. 차 이 는 바로 찾 는 복잡 도 에 있다 고 생각한다. 이번에 배 웠 다.
그리고 입력 데이터 양 이 많아 서 char 가 처리 하기 어렵 습 니 다. string 을 사용 하 는 것 을 권장 합 니 다.
또 뭐 가 있 는 것 같 아 요. dfs 순서 + AC 자동 동기 + 트 리 배열 의 방법 은 어차피...

#include
using namespace std;
const int MAXN=20;
const int MX=1e6+10;

struct bits_Aho_trie
{
    int next[MX][26],endd[MX],fail[MX];
    int root[MAXN],siz[MAXN],gcnt,ncnt,scnt;
    string str[300010];
    void init()
    {
        memset(root,0,sizeof(root));
        memset(siz,0,sizeof(siz));
        ncnt=gcnt=scnt=0;
    }
    int newnode()
    {
        endd[++ncnt]=fail[ncnt]=0;
        memset(next[ncnt],0,sizeof(next[ncnt]));
        return ncnt;
    }
    void build(int rt)
    {
        fail[rt]=rt;
        queuequ;
        for(int i=0;i<26;i++)
        {
            if(next[rt][i]) fail[next[rt][i]]=rt,qu.push(next[rt][i]);
            else next[rt][i]=rt;
        }
        while(!qu.empty())
        {
            int u=qu.front();qu.pop();
            endd[u]+=endd[fail[u]];
            for(int i=0;i<26;i++)
            {
                if(next[u][i])
                    fail[next[u][i]]=next[fail[u]][i],qu.push(next[u][i]);
                else
                    next[u][i]=next[fail[u]][i];
            }
        }
    }
    void rebuild(int l,int r,int rt)
    {
        rt=newnode();
        for(int i=l;i<=r;i++)
        {
            int p=rt;
            for(int j=0;j=2&&siz[gcnt-1]==siz[gcnt])
            siz[--gcnt]*=2;
        ncnt=root[gcnt]-1;
        rebuild(scnt-siz[gcnt]+1,scnt,root[gcnt]);
    }
    int rquery(int rt,string s)
    {
        int res=0,p=rt;
        for(int i=0;i>T;
    while(T--)
    {
        ac.init();
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>tmp;
            ac.Insert(tmp);
        }
        for(int i=0;i>x>>tmp;
            if(x==1)
                ac.Insert(tmp);
            else
                cout<