【悬2关】AC自动机模板 WA on#2求调
查看原帖
【悬2关】AC自动机模板 WA on#2求调
373198
WhileTrueRP楼主2023/12/20 09:39
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s;
struct node{
	int a[28];
	int cnt;
	int c,fa;
}trie[N];
int fail[N];
int size = 0;
void insert(string s){
	int p = 0;
	for(int i=0;i<s.length();i++){
		int now = s[i]-'a'+1;
		if(trie[p].a[now] == 0){
			trie[p].a[now] = ++size;
			trie[size].c = now;
			trie[size].fa = p;
		}
		p = trie[p].a[now];
	}
	trie[p].cnt ++;
	return;
}
void init(){
	queue<int> q;
	fail[0] = 0;
	for(int i=1;i<=26;i++){
		if(trie[0].a[i] != 0){
			q.push(trie[0].a[i]);
		}
	}
	while(!q.empty()){
		int now = q.front();
		q.pop();
		fail[now] = trie[fail[trie[now].fa]].a[trie[now].c];
		if(fail[now] == now){
			fail[now] = 0;
		}
		for(int i=1;i<=26;i++){
			if(trie[now].a[i] != 0){
				q.push(trie[now].a[i]);
			} 
		}
		
	}
	return;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>s;
		insert(s);
	}
	cin>>s;
	init();
	int len = s.length(),j = 0,ans = 0;
	for(int i=0;i<len;i++){
		bool flag = false;
		int now =  s[i]-'a'+1;
		while(trie[j].a[now] == 0){
			j = fail[j];
			if(flag){
				break;
			}else if(j == 0){
				flag = true;
			} 
		}
		j = trie[j].a[now];
		ans += trie[j].cnt;
		trie[j].cnt = 0;
	}
	printf("%d",ans);
}
2023/12/20 09:39
加载中...