Visits: 408

CF547E Mike and Friends

题意

• 给定 $n$ 个字符串 $s_{1 \dots n}$。
• $q$ 次询问 $s_k$ 在 $s_{l \dots r}$ 中出现了多少次。
• $n, \sum |s| \le 2 \times 10^5$，$q \le 5 \times 10^5$。

题解

首先对 $n$ 个字符串建出 AC 自动机。

将询问离线并差分成两个询问。

将字符串顺着扫一遍，对扫过的字符串在 trie 上的所有节点贡献 $+1$。

假设此时扫到串 $i$，那么在 $i$ 上的询问 $s_k$ 的贡献等于 $s_k$ 在 trie 上的终点在 fail 树上的子树贡献和。

按 fail 树的 dfs 序建树状数组维护即可，时间复杂度 $\mathcal O((n + q) \log n)$。

代码

const int N = 2e5 + 7, M = 26, Q = 5e5 + 7;
int n, m, q, p[N], trie[N][M], fail[N], f[N], t = 1, dfn[N], num, siz[N], c[N], k[Q], ans[Q];
char s[N];
vi e[N];

inline int ins(int n) {
    int p = 1;
    for (int i = 1; i <= n; i++) {
        int c = s[i] - 'a';
        if (!trie[p][c]) f[trie[p][c]=++t] = p;
        p = trie[p][c];
    }
    return p;
}

void dfs(int x) {
    dfn[x] = ++num, siz[x] = 1;
    for (ui i = 0; i < e[x].size(); i++) dfs(e[x][i]), siz[x] += siz[e[x][i]];
}

inline void build() {
    queue< int > q;
    for (int i = 0; i < M; i++)
        if (trie[1][i]) fail[trie[1][i]] = 1, q.push(trie[1][i]);
        else trie[1][i] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < M; i++)
            if (trie[x][i]) fail[trie[x][i]] = trie[fail[x]][i], q.push(trie[x][i]);
            else trie[x][i] = trie[fail[x]][i];
    }
    for (int i = 2; i <= t; i++) e[fail[i]].pb(i);
    dfs(1);
}

inline void add(int x) {
    while (x <= t) ++c[x], x += x & -x;
}

inline int ask(int x) {
    int ret = 0;
    while (x) ret += c[x], x -= x & -x;
    return ret;
}

int main() {
    rd(n), rd(q);
    for (int i = 1; i <= n; i++) rds(s, m), p[i] = ins(m);
    build();
    for (int i = 1; i <= n; i++) e[i].clear();
    for (int i = 1, l, r; i <= q; i++) {
        rd(l), rd(r), rd(k[i]);
        if (l > 1) e[l-1].pb(-i);
        e[r].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        int x = p[i];
        while (x ^ 1) add(dfn[x]), x = f[x];
        for (ui j = 0; j < e[i].size(); j++) {
            int o = e[i][j] > 0 ? 1 : -1, t = abs(e[i][j]), x = p[k[t]];
            ans[t] += o * (ask(dfn[x] + siz[x] - 1) - ask(dfn[x] - 1));
        }
    }
    for (int i = 1; i <= q; i++) print(ans[i]);
    return 0;
}