#2TLE求调
查看原帖
#2TLE求调
573860
Himemushi_Momoyo楼主2023/2/11 11:23
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct trie{
	trie *ch[30];
	trie *fail;
	int cnt; 
	trie(){
		memset(ch,NULL,sizeof(ch));
		fail=NULL;
		cnt=0;
	}
};
trie *root,*superoot;
void init(){
	root=new trie;
	superoot=new trie;
	root->fail=superoot;
	for(int i=0;i<26;i++){
		superoot->ch[i]=root;
	}
	superoot->cnt=-1;
}
void insert(char *str){
	trie *t=root;
	int len=strlen(str);
	for(int i=0;i<len;i++){
		int c=str[i]-'a';
		//cout<<c<<endl;
		if(t->ch[c]==NULL){
			t->ch[c]=new trie;
		}
		//cout<<"do"<<endl;
		t=t->ch[c];
	}
	t->cnt++;
}
queue<trie *> q;
void build_ac(){
	q.push(root);
	trie *t;
	while(!q.empty()){
		t=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(t->ch[i]==NULL){
				t->ch[i]=t->fail->ch[i];
			}
			else{
				t->ch[i]->fail=t->fail->ch[i];
				q.push(t->ch[i]);
			}
		}
	}
}
int query(char *str){
	int len=strlen(str);
	trie *t=root;
	int ans=0;
	for(int i=0;i<len;i++){
		int c=str[i]-'a';
		t=t->ch[c];
		for(trie *u=t;u->cnt!=-1;u=u->fail){
			ans+=u->cnt;
			u->cnt=-1;
		}
	}
	return ans;
}
int n;
char s[N];
int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cout.sync_with_stdio(false);
	cin>>n;
	init();
	for(int i=1;i<=n;i++){
		scanf("%s",s);
		insert(s);
	}
	//cout<<"do"<<endl;
	build_ac();
	//cout<<"do"<<endl;
	scanf("%s",s);
	cout<<query(s)<<endl;
	return 0;
}
2023/2/11 11:23
加载中...