AC自动机

https://www.luogu.com.cn/problem/P3808

简单版

\(n\) 个模式串和一个文本串，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

#include 
using namespace std;
#define LL long long
const int N = 1e6 + 10;
LL n;
char s[N];
struct ACA{
	LL trie[N][26], cnt[N], fail[N], idx = 0;
	void insert(char s[]){
		LL u = 0;
		for (int i = 0; s[i]; i ++ ){
			LL v = s[i] - 'a';
			if (!trie[u][v]) trie[u][v] = ++ idx;
			u = trie[u][v];
		}
		cnt[u] ++ ;
	}
	void get_fail(){
		queue  q;
		for (int i = 0; i < 26; i ++ )
			if (trie[0][i]){
				fail[trie[0][i]] = 0;
				q.push(trie[0][i]);
			}
		while (q.size()){
			LL u = q.front();
			q.pop();
			for (int v = 0; v < 26; v ++ ){
				if (trie[u][v]){
					fail[trie[u][v]] = trie[fail[u]][v];
					q.push(trie[u][v]);
				}
				else trie[u][v] = trie[fail[u]][v];
			}
		}
	}
	LL query(char s[]){
		LL u = 0, ans = 0;
		for (int i = 0; s[i]; i ++ ){
			u = trie[u][s[i] - 'a'];
			for (LL v = u; v && ~ cnt[v]; v = fail[v]){
				ans += cnt[v];
				cnt[v] = -1;
			}
		}
		return ans;
	}
}aca;
int main(){
	cin >> n;
	for (int i = 1; i <= n; i ++ ){
		cin >> s;
		aca.insert(s);
	}
	aca.get_fail();
	cin >> s;
	cout << aca.query(s) << "\n";
	return 0;
}