50求条
查看原帖
50求条
1373205
dg114514楼主2024/12/5 17:13

rt

#include<bits/stdc++.h> 
using namespace std;
struct ACAM{
	int trie[5000005][30],fail[5000005],cnt[5000005],tcnt,isget;
	queue<int>q;
	ACAM(){tcnt=0,isget=1;}
	void insert(const string& s){
		isget=0;
		int p=0,c;
		for(int i=0;i<s.size();i++){
			c=s[i]-97;
			if(!trie[p][c])trie[p][c]=++tcnt;
			p=trie[p][c];
		}
		cnt[p]++; 
	}
	void getFail(){
		while(!q.empty())q.pop();
		for(int i=0;i<26;i++)
			if(trie[0][i])
				fail[i]=0,q.push(i);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=0;i<26;i++)
				if(trie[u][i]) fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]);
				else trie[u][i]=trie[fail[u]][i];
		}
		isget=1;
	}
	int query(const string& s){
		if(!isget)getFail();
		int p=0,sum=0;
		for(int i=0;i<s.size();i++)
			for(int j=p=trie[p][s[i]-97];j&&~cnt[j];j=fail[j])
				sum+=cnt[j],cnt[j]=-1;
		return sum;
	}
}wa;
int main(){
	int n;
	cin>>n;
	string s;
	while(n--)
		cin>>s,wa.insert(s);
	cin>>s;
	cout<<wa.query(s);
}
2024/12/5 17:13
加载中...