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
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1000100;
char s[N];
struct ACAuto{
    int ch[N][26];
    int f[N], last[N];
    bool ban[N];
    int sz;
    void init(){
        ban[0] = 0;
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
    }
    int idx(char c){
        return c-'a';
    }
    void insert(){
        int len = strlen(s);
        int u = 0;
        for(int i=0; i<len; i++){
            int c = idx(s[i]);
            if(!ch[u][c]){
                memset(ch[sz],0,sizeof(ch[sz]));
                ban[sz]=0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX