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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000001;
struct node {
    int cnt;
    node* p[26], *fa, *fail;
    node() {
        cnt = 0;
    }
}e[maxn]; int ne = 0;
node* root = e + ne ++;
node* newnode(node* pre) {
    node* now = e + ne ++;
    now-> fa = pre;
    return now;
}
void insert(char* s) {
    node* now = root;
    for(int i = 1; i <= (int)strlen(s + 1); ++ i) {
        int index = (int)s[i] - 'a';
        if(!now-> p[index]) now-> p[index] = newnode(now);
        now = now-> p[index];
        if(i == (int)strlen(s + 1)) now-> cnt++;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX