AC自动机相关模板

P5357

#include <bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;

int n, cnt[N] = {0};
string s[N], t;

map<string, int> apr;

string reads() {
	string s;
	char ch = getchar();
	while (ch < 'a' || ch > 'z')
		ch = getchar();
	while (ch >= 'a' && ch <= 'z')
		s += ch, ch = getchar();
	return s;
}

struct ACauto {
	int n, nxt[N][26], fail[N], node[N];
	int to[N], next[N], head[N], tot = 0;
	void init() {
		n = 0;
		memset(nxt, 0, sizeof nxt);
		memset(fail, 0, sizeof fail);
		memset(node, 0, sizeof node);
	}
	void add(string s, int id) {
		int cur = 0;
		for (int i = 0; i < s.size(); i++) {
			if (!nxt[cur][s[i] - 'a'])	
				nxt[cur][s[i] - 'a'] = ++n;
			cur = nxt[cur][s[i] - 'a'];
		}
		node[id] = cur;
	}
	void pre() {
		queue<int> q;
		for (int i = 0; i < 26; i++)
			if (nxt[0][i])
				q.push(nxt[0][i]);
		while (!q.empty()) {
			int tmp = q.front();
			q.pop();
			for (int i = 0; i < 26; i++)
				if (nxt[tmp][i])
					fail[nxt[tmp][i]] = nxt[fail[tmp]][i], q.push(nxt[tmp][i]);
				else
					nxt[tmp][i] = nxt[fail[tmp]][i]; 
		}
	}
	void qry(string s) {
		int cur = 0;
		for (int i = 0; i < s.size(); i++)
			cur = nxt[cur][s[i] - 'a'], cnt[cur]++;
	}
	void add(int u, int v) {
		to[++tot] = v, next[tot] = head[u], head[u] = tot;
	}
	void dfs(int p){
	    for (int i = head[p]; i; i = next[i])
	        dfs(to[i]), cnt[p] += cnt[to[i]];
	}
	void intot() {
		for (int i = 1; i <= n; i++)
			add(fail[i], i);
		dfs(0);
	}
} ac;

signed main() {
	ac.init();
	cin >> n;
	for (int i = 1; i <= n; i++) {
		s[i] = reads();
		if (!apr[s[i]]) {
			apr[s[i]] = i;
			ac.add(s[i], i);
		}
	}
	ac.pre();
	ac.qry(reads());
	ac.intot();
	for (int i = 1; i <= n; i++)
		printf("%lld\n", cnt[ac.node[apr[s[i]]]]);
	return 0;
}