不知道哪错了
查看原帖
不知道哪错了
464528
见贤思齐_Seakies楼主2022/4/30 17:51
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 9;
int trie[MAXN][30], sum[MAXN];
int fail[MAXN];
void insert(string s) {
	int root = 0, tot = 0;
	for (int i = 0; i < s.size(); i++) {
		int ch = s[i] - 'a';
		if (!trie[root][ch]) trie[root][ch] = ++tot;
		root = trie[root][ch];
	}
	sum[root]++;
}
void get_fail() {
	queue<int> q;
	for (int i = 0; i < 26; i++) {
		if (trie[0][i]) {
			fail[trie[0][i]] = 0;
			q.push(trie[0][i]);
		}
	}
	while (!q.empty()) {
		int root = q.front();
		q.pop();
		int fafail = fail[root];
		for (int i = 0; i < 26; i++) {
			if (trie[root][i]) {
				fail[trie[root][i]] = trie[fafail][i];
				q.push(trie[root][i]);
			} else trie[root][i] = trie[fafail][i];
		}
	}
}
int AC_query(string s) {
	int root = 0, ans = 0;
	for (int i = 0; i < s.size(); i++) {
		int ch = s[i] - 'a';
		while (!trie[root][ch] && sum[trie[root][ch]] != -1) {
			ans += sum[trie[root][ch]];
			sum[trie[root][ch]] = -1;
			root = fail[trie[root][ch]];
		}
		root = trie[root][ch];
	}
	return ans;
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		insert(s);
	}
	get_fail();
	string t;
	cin >> t;
	cout << AC_query(t) << endl;
	return 0;
}
2022/4/30 17:51
加载中...