题解 CF547E 【Mike and Friends】
xht
2019-12-09 02:22:21
> [CF547E Mike and Friends](https://codeforc.es/contest/547/problem/E)
## 题意
- 给定 $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)$。
## 代码
```cpp
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;
}
```