【模板】AC自动机

(AC)自动机又称 (Trie) 图，是一个确定性有限状态自动机。具体来讲，通过在 (trie) 上定义一个 (fail) 转移函数，将 (trie) 的树形结构变成了一个图的结构。同时，根据 (DFA) 的性质，对于每个状态节点都要有关于字母表中所有字符的转移方式，在构建 (fail) 指针的同时，也完成了这个操作。
(AC)自动机建立的时间复杂度为 (O(N))，匹配的时间复杂度为 (O(M))，其中 (N) 为所有模式串长度的总和，(M) 为匹配串长度的总和。

代码如下

#include <bits/stdc++.h>
using namespace std;

struct trie {
	struct node {
		int go[26], cnt;
		node() : cnt(0) {
			memset(go, -1, sizeof(go));
		}
	};
	vector<node> t;
	vector<int> fail;
	int rt;
	trie() : rt(0) {
		t.emplace_back(node());
	}
	void insert(const string &s) {
		int now = rt;
		for (auto ch : s) {
			if (t[now].go[ch - 'a'] == -1) {
				t[now].go[ch - 'a'] = t.size();
				t.emplace_back(node());
			}
			now = t[now].go[ch - 'a'];
		}
		t[now].cnt++;
	}
	void build_fail() {
		fail.resize(t.size());
		queue<int> q;
		for (int i = 0; i < 26; i++) {
			if (t[rt].go[i] == -1) {
				t[rt].go[i] = rt;
			} else {
				q.push(t[rt].go[i]);
			}
		}
		while (q.size()) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < 26; i++) {
				if (t[u].go[i] != -1) {
					fail[t[u].go[i]] = t[fail[u]].go[i];
					q.push(t[u].go[i]);
				} else {
					t[u].go[i] = t[fail[u]].go[i];
				}
			}
		}
	}
	int search(const string &s) {
		int now = rt, ret = 0;
		for (auto ch : s) {
			now = t[now].go[ch - 'a'];
			for (int i = now; i && t[i].cnt != -1; i = fail[i]) {
				ret += t[i].cnt;
				t[i].cnt = -1;
			}
		}
		return ret;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	trie t;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		t.insert(s);
	}
	t.build_fail();
	string s;
	cin >> s;
	cout << t.search(s) << endl;
	return 0;
}