题目地址：洛谷：【P2336】[SCOI2012]喵星球上的点名 – 洛谷、BZOJ：Problem 2754. — [SCOI2012]喵星球上的点名

题目描述

a180285 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。
假设课堂上有 N 个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。
然而，由于喵星人的字码过于古怪，以至于不能用 ASCII 码来表示。为了方便描述，a180285 决定用数串来表示喵星人的名字。
现在你能帮助 a180285 统计每次点名的时候有多少喵星人答到，以及 M 次点名结束后每个喵星人答到多少次吗？

输入输出格式

输入格式：
现在定义喵星球上的字符串给定方法：
先给出一个正整数 L ，表示字符串的长度，接下来L个整数表示字符串的每个字符。
输入的第一行是两个整数 N 和 M。
接下来有 N 行， 每行包含第 i 个喵星人的姓和名两个串。 姓和名都是标准的喵星球上的字符串。
接下来有 M 行，每行包含一个喵星球上的字符串，表示老师点名的串。

输出格式：
对于每个老师点名的串输出有多少个喵星人应该答到。
然后在最后一行输出每个喵星人被点到多少次。

输入输出样例

输入样例#1：

2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25

输出样例#1：

2
1
0
1 2

说明

对于30%的数据，保证：
1 ≤ N ,M ≤ 1000 喵星人的名字总长不超过 4000，点名串的总长不超过 2000，
对于100%的数据，保证：
1 ≤ N ≤ 20000， 1 ≤ M ≤ 50000 喵星人的名字总长和点名串的总长分别不超过100000
保证喵星人的字符串中作为字符存在的数不超过10000

题解

AC自动机暴力

考虑一个AC自动机的暴力做法。首先因为字符集大小并不确定，而且可能很大，我们要考虑map存儿子。接着因为字符集大小不确定我们没办法加虚边了只能暴力跳fail。这导致了最后洛谷#11 TLE的惨案。
我们考虑把点名串扔进去，把姓名用一个非法字符连接起来来匹配。每匹配到一个点名串在点名串的计数器上+1，然后统计这个姓名匹配到了多少点名串。
记录该点是否被访问过的数组vis开的很大，最好不要memset，用一个栈记下修改过的节点最后改回去。
我加了一堆register，全部inline，能避免STL的改手写，加了fread，然而还是敌不过洛谷的#11 QAQ！
所以说这是个AC自动机暴力啦，我也不会fail树高论，也不会SA，就这样吧，以后学了SA再来A这题。
对不起，SA真的是能为所欲为的！

fail树优化

如果我们将AC自动机中所有fail指针（未路径压缩）反向建有向边，会得到一棵以0为根方向向叶子节点的有向树。利用fail树的有关性质，我们可以把字符串匹配问题转换成树上问题，优化复杂度。本题中也可以使用该种算法。
首先我们可以类似的在姓名中间加一个不会出现的字符，这里我用的是-1，插入Trie树中，然后计算fail指针建立fail树。需要注意的是fail指针无法路径压缩，因此只能暴力跳fail来找。为了方便，后面建树的时候对节点编号+1处理了一下，避免0的特判。事实证明，这一操作为后面的处理带来了不少的麻烦，许多地方忘记+1换算了。有了fail树以后，我们要利用fail树的相关性质解决题目问题。
对于问题1，是求一个模式串出现在哪些文本串中了，这个问题可以转化为一个模式串的末尾点在fail树的子树中有多少不同文本串的节点。这是由于，文本串中出现过的模式串位置末尾的fail指针会指向这一模式串的末尾，由于反向，就变成了模式串末尾指向文本串节点了，那就是一个子树问题。这个问题可以转化成一个DFS序序列上的数颜色种数问题，这让我们想起了[SDOI2009]HH的项链一题，采用相同的树状数组+扫描线的做法即可求出。因此，我们需要标注每个节点属于哪个文本串这样一个颜色信息，并且处理出一个每个颜色有哪些点的链表，方便扫描线维护信息。如果文本串很多，我们不可能每次都枚举一下每个颜色，因此不如再开个链表记录一下每个点上有几种颜色。链表空间紧凑，适合用来做这种不确定空间且不需要随机查找的统计问题。另外还要处理出子树大小，方便确定查询区间。上述信息处理完毕以后，就是上面那个省选题的做法了。这一部分的复杂度是O(n \log n)的。
对于问题2，求一个文本串中出现过几种模式串。如果我们默认每个节点初始权值为0，而对每个模式串结尾节点的权值加1，则模式串到树根路径上的点权和就是这个点为结尾的后缀为模式串的个数，如果将文本串上每个节点到树根的路径求并求权值和，就是我们要的答案了。树链的并我们可以用树链剖分+线段树区间染色求和的方式来求，这样做则是O(n \log^2 n)的。如果想只有一个log，可以用将节点按照DFS序排序后的顺序统计信息，加入第i个节点的时候，减去i与i-1节点的LCA到树根的路径权值和，这样可以避免这一段公共路径权值和被计入两次，起到了去重的效果。求LCA采用倍增法，则复杂度可以降为O(n \log n)了。
但是我们仔细想一下，这些内容都很长。我们需要Trie树的插入和统计信息，需要两个链表分别维护一个节点上的颜色种类和一个颜色涉及的节点数，需要一个树状数组，需要一个树DFS统计树信息，需要一个倍增LCA的处理，需要一个离线处理区间颜色数的算法，需要一个按DFS序排序去重的计数算法。以上就是写出这道题的这种解法的所有需求，接下来就是一步一步地去实现它们了。
在实现过程中，遇到了种种问题，最困惑我的一点就是写代码的时候DFS序号和节点序号搞混了，以及节点序号+1忘记了，不过如果能够自己实现一遍，相信是很锻炼代码能力和调试能力的。这个题今天花了一天来做，收获也很大。

代码

AC自动化暴力

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <map>
#include <vector>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define readint ip.read

const int MAXN = 100005, MAXL = 100005;

int n, m;
std::vector<int> names[MAXN], val[MAXL];
int fail[MAXL], cnt;
std::map<int, int> ch[MAXL];
int que[MAXL], l, r;

inline void insert(int id) {
    register int len = readint(), p = 0;
    for(register int i = 0; i < len; i++) {
        int t = readint();
        if(!ch[p][t]) ch[p][t] = ++cnt;
        p = ch[p][t];
    }
    val[p].push_back(id);
}

inline void calfail() {
    l = r = 0;
    fail[0] = 0;
    for(std::map<int, int>::iterator it = ch[0].begin(); it != ch[0].end(); it++) {
        register int u = it->second;
        que[r++] = u;
        fail[u] = 0;
    }
    while(l != r) {
        register int u = que[l++];
        for(std::map<int, int>::iterator it = ch[u].begin(); it != ch[u].end(); it++) {
            int t = it->first, v = it->second, p = fail[u];
            while(p && !ch[p][t]) p = fail[p];
            fail[v] = ch[p][t];
            que[r++] = v;
        }
    }
}

int ctn[MAXN], qur[MAXN];
bool vis[MAXL];
int sta[MAXL], stot;

inline int calcnt(int p) {
    register int res = 0;
    for(; p; p = fail[p]) {
        if(vis[p]) break;
        vis[p] = true;
        sta[++stot] = p;
        for(register int i = 0; i < val[p].size(); i++) {
            res++;
            qur[val[p][i]]++;
        }
    }
    return res;
}

inline void query(int id) {
    register int p = 0;
    stot = 0;
    for(register int i = 0; i < names[id].size(); i++) {
        int t = names[id][i];
        while(p && !ch[p][t]) p = fail[p];
        p = ch[p][t];
        ctn[id] += calcnt(p);
    }
    for(register int i = 1; i <= stot; i++) {
        vis[sta[i]] = false;
    }
}

int main() {
    n = readint(); m = readint();
    for(register int i = 1; i <= n; i++) {
        register int len = readint();
        while(len--) names[i].push_back(readint());
        names[i].push_back(-1);
        len = readint();
        while(len--) names[i].push_back(readint());
    }
    for(register int i = 1; i <= m; i++) {
        insert(i);
    }
    calfail();
    for(register int i = 1; i <= n; i++) {
        query(i);
    }
    for(register int i = 1; i <= m; i++) {
        printf("%d\n", qur[i]);
    }
    for(register int i = 1; i <= n; i++) {
        printf("%d ", ctn[i]);
    }
    return 0;
}

fail树优化（附注释）

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <map>
#include <queue>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 200005;

// 双向链表 
struct LinkedList {
    int head[MAXN], tail[MAXN], val[MAXN], pre[MAXN], nxt[MAXN], tot;
    LinkedList() {
        tot = 0;
    }
    // 在p所属的链表头部插入v这个值 
    inline void insert(int p, int v) {
        tot++; 
        if(!tail[p]) tail[p] = tot;
        val[tot] = v; if(head[p]) pre[head[p]] = tot; nxt[tot] = head[p]; head[p] = tot;
    }
} col, col2;

// 树状数组 
struct BinaryIndexTree {
    int tr[MAXN];
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int x, int v) {
        for(int i = x; i < MAXN; i += lowbit(i)) {
            tr[i] += v;
        }
    }
    inline int query(int x) {
        int res = 0;
        for(int i = x; i; i -= lowbit(i)) {
            res += tr[i];
        }
        return res;
    }
} bit;

// 字符集太大，用map存儿子省空间 
std::map<int, int> ch[MAXN];
std::queue<int> que;
std::vector<int> gra[MAXN]; // fail树存在这里 
int fail[MAXN], ecnt[MAXN], end[MAXN], tot;

// Trie树的插入，分别处理文本串和模式串 
inline void insert(std::vector<int> &str, int id, bool isname) {
    int p = 0;
    for(int i = 0; i < str.size(); i++) {
        int t = str[i];
        if(!ch[p][t]) {
            ch[p][t] = ++tot;
        }
        if(isname) {
            // 统计每个节点上的颜色种类 
            col.insert(ch[p][t] + 1, id);
        }
        p = ch[p][t];
    }
    if(!isname) {
        // 统计一个节点是多少模式串的结尾，模式串可能有多个相同不可用bool 
        ecnt[p + 1]++; end[id] = p + 1;
    }
}

// 计算fail数组 
inline void calfail() {
    for(std::map<int, int>::iterator it = ch[0].begin(); it != ch[0].end(); it++) {
        que.push(it->second);
        gra[1].push_back(it->second + 1);
    }
    while(!que.empty()) {
        int p = que.front(); que.pop();
        for(std::map<int, int>::iterator it = ch[p].begin(); it != ch[p].end(); it++) {
            int t = fail[p], q = it->second;
            // 暴力跳fail计算 
            while(!ch[t][it->first] && t) t = fail[t];
            fail[q] = ch[t][it->first];
            gra[ch[t][it->first] + 1].push_back(q + 1);
            que.push(q);
        }
    }
}

int anc[MAXN][20], siz[MAXN], dfn[MAXN], dep[MAXN], ptn[MAXN], sum[MAXN], clk;

// DFS处理fail树信息 
inline void dfs(int u) {
    siz[u] = 1; dfn[u] = ++clk; ptn[dfn[u]] = u;
    sum[u] = sum[anc[u][0]] + ecnt[u];
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == anc[u][0]) continue;
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        dfs(v);
        siz[u] += siz[v];
    }
}

int n, m;

struct Query {
    int id, l, r;
    inline bool operator<(const Query &rhs) const {
        return l == rhs.l ? r < rhs.r : l < rhs.l;
    }
} qur[MAXN];

// 第一个问题

int ans1[MAXN];

inline void main1() {
    // 按DFS序处理出每个颜色的链表 
    for(int i = 1; i < MAXN; i++) {
        for(int j = col.head[ptn[i]]; j; j = col.nxt[j]) {
            int c = col.val[j];
            col2.insert(c, i);
        }
    }
    // 初始化询问以及对询问排序 
    for(int i = 1; i <= m; i++) {
        qur[i] = Query {i, dfn[end[i]], dfn[end[i]] + siz[end[i]] - 1};
    }
    // 初始化树状数组，在每个颜色的初位置+1 
    for(int i = 1; i <= n; i++) {
        bit.add(col2.val[col2.tail[i]], 1);
    }
    std::sort(qur + 1, qur + m + 1);
    int lst = 1;
    // 同[SDOI2009]HH的项链
    for(int i = 1; i <= m; i++) {
        if(lst != qur[i].l) {
            for(int j = lst; j < qur[i].l; j++) {
                for(int k = col.head[ptn[j]]; k; k = col.nxt[k]) {
                    int c = col.val[k];
                    bit.add(j, -1);
                    col2.tail[c] = col2.pre[col2.tail[c]];
                    if(col2.val[col2.tail[c]]) bit.add(col2.val[col2.tail[c]], 1);
                }
            }
            lst = qur[i].l;
        }
        ans1[qur[i].id] = bit.query(qur[i].r);
    }
    for(int i = 1; i <= m; i++) {
        printf("%d\n", ans1[i]);
    }
}

// 倍增LCA
inline void preparelca() {
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i < MAXN; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

inline int querylca(int x, int y) {
    if(dep[x] > dep[y]) std::swap(x, y);
    int del = dep[y] - dep[x];
    for(int i = 19; i >= 0; i--) {
        if(del & (1 << i)) {
            y = anc[y][i];
        }
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--) {
        if(anc[x][i] != anc[y][i]) {
            x = anc[x][i]; y = anc[y][i];
        }
    }
    return anc[x][0];
}

// 第二个问题 

std::vector<int> name[MAXN];
int ans2[MAXN];

inline bool cmp(int a, int b) {
    return dfn[a] < dfn[b];
}

inline void main2() {
    for(int i = 1; i <= n; i++) {
        int p = 0;
        // 将字符串换成该字符串的节点 
        for(int j = 0; j < name[i].size(); j++) {
            p = ch[p][name[i][j]];
            name[i][j] = p + 1;
        }
        // 按DFS序计算树链的并的权值和 
        std::sort(name[i].begin(), name[i].end(), cmp);
        for(int j = 0; j < name[i].size(); j++) {
            ans2[i] += sum[name[i][j]];
            if(j) ans2[i] -= sum[querylca(name[i][j], name[i][j - 1])];
        }
    }
    for(int i = 1; i <= n; i++) {
        printf("%d ", ans2[i]);
    }
}

int len;
std::vector<int> s;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        s.clear();
        len = readint();
        while(len--) {
            s.push_back(readint());
        }
        s.push_back(-1);
        len = readint();
        while(len--) {
            s.push_back(readint());
        }
        insert(s, i, true);
        name[i] = s;
    }
    for(int i = 1; i <= m; i++) {
        s.clear();
        len = readint();
        while(len--) {
            s.push_back(readint());
        }
        insert(s, i, false);
    }
    calfail();
    dfs(1);
    preparelca();
    main1();
    main2();
    return 0;
}