【题解】[SCOI2012] 喵星球上的点名 BZOJ – 2754

题目戳我

这是 SAM 模板题，然而槽点其实挺多的吧

比如为啥要姓名分开，完全没意义啊

而且字符集开到 $10 ^ 4$有啥意义啊

做法很简单，用姓名串建广义 SAM

姓和名直接用一个不存在的字符（比如 $-1$）连起来就行了

字符集大用 map 就行了

然后第一问就是求点名串对应的节点是多少个姓名的子串，这个东西可以在建完 SAM 后再用姓名串扫一遍，姓名串遍历 SAM 的途中向上暴力跳 fail，跳到的点的 ans++，之前跳过的点就不用跳了。根据势能分析这个是和建 SAM 一个复杂度的。当然如果点名串中途适配了答案就为 $0$

第二问就是求每个姓名串的子串被多少个不同的点名串点到了。这个在点名串遍历完 SAM 的时候在最终到达的节点处打一个标记，然后某个姓名串的答案就是它子串的标记个数，也是暴力条 fail 统计，跳过的就不用继续跳，复杂度依然同建 SAM

值得注意的是广义后缀自动机建图复杂度上限是 $O(n \sqrt n)$的（百度上那位说期望 $O(n \sqrt n)$的是咋搞的），然而还是跑得很快的

代码：

#include <bits/stdc++.h>

#define NS (150005)

using namespace std;

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m;

short A[NS << 1], B[NS];

struct SAM
{
    struct N
    {
        map<short, int> nxt;
        int l, f, sz;
        int &operator [] (const short a) { return nxt[a]; }
    } e[NS << 1];
    int lst, sz;
    SAM() { sz = 1; }
    void push(short c)
    {
        int a = ++sz, p = lst;
        e[a].l = e[p].l + 1, lst = a;
        while (p && !e[p][c]) e[p][c] = a, p = e[p].f;
        if (!p) { e[a].f = 1; return; }
        int q = e[p][c];
        if (e[q].l == e[p].l + 1) { e[a].f = q; return; }
        int nq = ++sz;
        e[nq] = e[q], e[nq].l = e[p].l + 1, e[q].f = e[a].f = nq;
        while (e[p][c] == q) e[p][c] = nq, p = e[p].f;
    }
    void insert(short *s)
    {
        lst = 1;
        for (int i = 1; i <= s[0]; i += 1) push(s[i]);
    }
    int vis[NS << 1], tag[NS << 1];
    void fresh(short *s)
    {
        int a = 1;
        vis[0]++;
        for (int i = 1, p; i <= s[0]; i += 1)
        {
            p = a = e[a][s[i]];
            while (p && vis[p] != vis[0])
                e[p].sz++, vis[p] = vis[0], p = e[p].f;
        }
    }
    void run(short *s)
    {
        int a = 1;
        for (int i = 1; a && i <= s[0]; i += 1) a = e[a][s[i]];
        if (!a) { puts("0"); return; }
        printf("%d\n", e[a].sz), tag[a]++;
    }
    void clear(short *s)
    {
        int a = 1, ans = 0;
        vis[0]++;
        for (int i = 1, p; i <= s[0]; i += 1)
        {
            p = a = e[a][s[i]];
            while (p && vis[p] != vis[0])
                ans += tag[p], vis[p] = vis[0], p = e[p].f;
        }
        printf("%d ", ans);
    }
} sam;

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    short *p = A;
    for (int i = 1, a; i <= n; i += 1)
    {
        IN(a);
        for (int i = 1; i <= a; i += 1) IN(p[i]);
        IN(p[0]), p[a + 1] = -1, p[0] += a + 1;
        for (int i = a + 2; i <= p[0]; i += 1) IN(p[i]);
        sam.insert(p), p += p[0] + 1;
    }
    p = A;
    for (int i = 1; i <= n; i += 1) sam.fresh(p), p += p[0] + 1;
    for (int i = 1; i <= m; i += 1)
    {
        IN(B[0]);
        for (int i = 1; i <= B[0]; i += 1) IN(B[i]);
        sam.run(B);
    }
    p = A;
    for (int i = 1; i <= n; i += 1) sam.clear(p), p += p[0] + 1;
    return 0;
}