RE求调
查看原帖
RE求调
1286552
ice_shooter楼主2025/7/24 14:52
#include<bits/stdc++.h>
using namespace std;
struct Trie{
	int cnti=0;
	Trie *son[26]={},*next=NULL;
}*top=new Trie;
void insert(string s){
	Trie *t=top;
	for(int i=0;i<s.size();i++){
		Trie *&p=t->son[s[i]-'a'];
		if(p==NULL)p=new Trie;
		t=p;
	}t->cnti++;
}void build(){
	queue<Trie*> q;
	for(int i=0;i<26;i++){
		if(top->son[i]!=NULL){
			q.push(top->son[i]);
			top->son[i]->next=top;
		}else{
			top->son[i]=top;
		}
	}while(q.size()){
		Trie *u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(u->son[i]!=NULL){
				if(u->next->son[i]!=NULL)u->son[i]->next=u->next->son[i];
				else u->son[i]->next=top;
				q.push(u->son[i]);
			}else{
				if(u->next->son[i]!=NULL)u->son[i]=u->next->son[i];
				else u->son[i]=top;
			}
		}
	}
}int query(string s){
	int cnti=0;
	Trie *p=top;
	for(int i=0;i<s.size();i++){
		p=p->son[s[i]-'a'];
		Trie *t=p;
		while(t!=top && t!=NULL && t->cnti!=-1){
			cnti+=t->cnti;
			t->cnti=-1;
			t=t->next;
		}
	}return cnti;
}int n;
string s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s;
		insert(s);
	}cin>>s;
	cout<<query(s);
	return 0;
}
2025/7/24 14:52
加载中...