#2WA 输出3696 | 萌新刚学AC自动机,求调
查看原帖
#2WA 输出3696 | 萌新刚学AC自动机,求调
405894
233L楼主2021/6/7 19:50
#include<bits/stdc++.h>
#define N 1000004
using namespace std;
int n,top;
struct trie{
	int son[26];
	int f,fail;
}a[N];
void insert(string s){
	int f,p=0,len=s.size();
	for(int i=0;i<len;i++){
		f=s[i]-97;
		if(!a[p].son[f])
			a[p].son[f]=++top;
		p=a[p].son[f];
	}
	a[p].f++;
}
void getFail(){
	queue<int>q;
	int u,v,fail;
	q.push(0);
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			v=a[u].son[i];
			fail=a[u].fail;
			if(!v){
				a[u].son[i]=a[fail].son[i];
				continue;
			}
			a[v].fail=a[fail].son[i];
			q.push(v);
		}
	}
}
int find(string t){
	int f,k,ans=0,p=0,len=t.size();
	for(int i=0;i<len;i++){
		f=t[i]-97;
		p=a[p].son[f];
		k=p;
		while(a[k].f!=-1){
			ans+=a[k].f;
			a[k].f=-1;
			k=a[k].fail;
		}
	}
	return ans;
}
int main(){
	//freopen("P3808_2.in","r",stdin);
	string s,t;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s;
		insert(s);
	}
	cin>>t;
	getFail();
	cout<<find(t);
}
2021/6/7 19:50
加载中...