AC自动机 #2MLE 求助
查看原帖
AC自动机 #2MLE 求助
357163
shyr楼主2022/6/11 10:41
#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k;
queue<int> q;
char s[1000005];
struct TRIE{
	int s[27], c, fail;
}d[1000005];
void trie(){
	int i, j, p = 1;
	for(i = 0; s[i]; ++i){
		j = s[i] - 97;
		if(!d[p].s[j]) d[p].s[j] = ++k;
		p = d[p].s[j];
	}
	d[p].c++;
} 
int main(){
	scanf("%d", &n);
	for(i = 1; i <= n; ++i){
		scanf("%s", s);
		trie();
	}
	q.push(1);
	for(i = 1; i <= 26; ++i) d[0].s[i] = 1;
	while(q.size()){
		int a = q.front(); q.pop();
		for(int b = 1; b <= 26; ++b){
			if(d[a].s[b]){
				q.push(d[a].s[b]); 
				d[q.front()].fail = d[d[a].fail].s[b];
			}//预处理最长公共前后缀的位置 
			else{
				d[a].s[b] = d[d[a].fail].s[b]; 
			} //失配时走到哪里去 
		}
	}
	int ans = 0;
	scanf("%s", s + 1);
	for(i = k = 1; s[i]; ++i){
		j = s[i] - 97;
		k = d[k].s[j];
		ans += d[k].c, d[k].c = 0;
	} 
	printf("%d\n", ans);
	return 0;
}

mx对算法理解有限,有问题还请轻喷/kk

2022/6/11 10:41
加载中...