CF547E Mike and Friends 题解

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;
}