bzoj-3172单词[fail树]

fail树的性质：子节点是以父节点为后缀的串。
对于这道题，我们用num[]维护每个串出现的次数，在insert的时候对每个节点都要加一，表示这个节点已经出现过一次了。
最后我们构建fail树，然后把每个子节点的num都加到当前节点上就是这个串总共出现的次数了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
struct node{
    int nex[maxn][26], tot, root;
    int f[maxn], cnt, num[maxn];
    vector<int>G[maxn];
    int newnode() {
        for(int i = 0; i < 26; i++) {
            nex[tot][i] = -1;
        }
        return tot++;
    }
    void init() {
        tot = 0;
        root = newnode();
    }
    void insert(char *s, int &x) {
        int u = root, len = strlen(s);
        for(int i = 0; i < len;  i++) {
            int ch = s[i]-'a';
            if(nex[u][ch] == -1) {
                nex[u][ch] = newnode();
            }
            u = nex[u][ch];
            num[u]++;
        }
        x = u;
    }
    void getfail() {
        queue<int>Q;
        for(int i = 0; i < 26; i++) {
            if(nex[root][i] == -1) {
                nex[root][i] = root;
            }
            else {
                f[nex[root][i]] = root;
                Q.push(nex[root][i]);
            }
        }
        while(!Q.empty()) {
            int u = Q.front();Q.pop();
            for(int i = 0; i < 26; i++) {
                if(nex[u][i] == -1) {
                    nex[u][i] = nex[f[u]][i];
                }
                else {
                    f[nex[u][i]] = nex[f[u]][i];
                    Q.push(nex[u][i]);
                }
            }
        }
        for(int i = 1; i < tot; i++) {
            G[i].push_back(f[i]);
            G[f[i]].push_back(i);
        }
    }
    void dfs(int u, int fa) {
        int sz = G[u].size();
        for(int i = 0; i < sz; i++) {
            int v = G[u][i];
            if(v == fa) continue;
            dfs(v, u);
            num[u] += num[v];
        }
    } 
}ac;
int res[maxn];
char s[maxn];
int main() {
    int n;
    scanf("%d", &n);
    ac.init();
    for(int i = 1; i <= n; i++) {
        scanf("%s", s);
        ac.insert(s, res[i]);
    }
    ac.getfail();
    ac.dfs(ac.root, -1);
    for(int i = 1; i <= n; i++) {
        printf("%d\n", ac.num[res[i]]);
    }
}