AC自动机(指针)
查看原帖
AC自动机(指针)
443023
chenkuo楼主2023/10/10 17:59

样例也过不了,机房里的同学每一个会的

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s;
int wei(char a){return (int)(a-'a');}
struct trie{
	trie *next[26],*fail;
	int bj;
};
trie *root,*superRoot;
void csh(trie *u){
	u->bj=0;u->fail=NULL;
	for(int i=0;i<26;i++) u->next[i]=NULL;
}
void init(){
	root->fail=superRoot;
	for(int i=0;i<26;i++){
		superRoot->next[i]=root;
	}
	superRoot->bj=-1;
}
void build(string s){
	trie *ls,*place;
	place=root;
	for(int i=0;i<s.size();i++){
		int u=wei(s[i]);
		if(place->next[u]==NULL){
			ls=new trie;
			csh(ls);
			place->next[i]=ls;
		}else ls=place->next[u];
		place=ls;
	}
	place->bj++;
}
void build_ac(){
	queue<trie*>q;
	q.push(root);
	while(!q.empty()){
		trie *ls;
		ls=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ls->next[i]==NULL){
				ls->next[i]=ls->fail->next[i];
			}else{
				ls->next[i]->fail=ls->fail->next[i];
				q.push(ls->next[i]);
			}
		}
	}
}
void find(string s){
	trie *place=superRoot->next[0];
	for(int j=0;j<s.size();j++){
		int i=wei(s[j]);
		place=place->next[i];
		for(trie *ls=place;ls->bj!=-1;ls=ls->fail){
			ans+=ls->bj;
        	ls->bj=-1;
		}
	} 
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	root=new trie;csh(root);
	superRoot=new trie;csh(superRoot);
	init();
	for(int i=1;i<=n;i++){
		cin>>s;
		build(s);
	}
	build_ac();
	cin>>s;root=superRoot->next[0];
	find(s);
	printf("%d",ans);
}
/*
3
chenkuo
chenpingye
laojiang
chenkuochenkuolaojiangchenlaojiangchenpingyelaojiang
*/
2023/10/10 17:59
加载中...