模板求调
查看原帖
模板求调
884496
chtholly3楼主2023/4/11 11:35

#1 T,#2 M。。。 照着模板写的,实在不知道哪错了,请教一下各位大佬

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
char trie[maxn][26];
int cnt[maxn], idx;
int ne[maxn];
int ans;
char str[maxn];
void insert(char *s) {
	int now = 0;
	for (int i = 0;s[i]; i++)
	{
		int tmp = s[i] - 'a';
		if (!trie[now][tmp])trie[now][tmp] = ++idx;
		now = trie[now][tmp];
	}
	cnt[now]++;
}
void build() {//建AC自动机
	queue<int>q;
	for (int i = 0; i < 26; i++)
		if (trie[0][i])
		{
			ne[trie[0][i]] = 0;
			q.push(trie[0][i]);
		}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < 26; i++)
		{
			int v = trie[u][i];
			if (v) {
				ne[v] = trie[ne[u]][i];
				q.push(v);
			}//有儿子就帮儿子建回跳边
			else trie[u][i] = trie[ne[u]][i];//没有儿子自己建转移边
		}
	}
}
void query(char *t) {
	for (int i = 0, k = 0; t[k]; k++)
	{
		i = trie[i][t[k] - 'a'];
		for (int j = i; j && ~cnt[j]; j = ne[j])
		{
			ans += cnt[j]; cnt[j] = -1;
		}
	}
}
int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		scanf("%s", str);
		insert(str);
	}
	build();
	scanf("%s",str);
	query(str);
	cout <<ans;
	return 0;
}
2023/4/11 11:35
加载中...