AC自动机#2WA求助
查看原帖
AC自动机#2WA求助
400333
qzilr楼主2022/7/13 11:51
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
struct node{
	int ch[26],v,fail;
}t[maxn];
int tot=0,n;
int idx(char c){
	return c-'a';
}
void insert(char s[]){
	int p=0,l=strlen(s);
	for(int i=0;i<l;i++){
		int c=idx(s[i]);
		if(!t[p].ch[c])	t[p].ch[c]=++tot;
		p=t[p].ch[c];
	}
	t[p].v++;
}
void make_fail(){
	queue<int> q;
	for(int i=0;i<26;i++)   if(t[0].ch[i])  q.push(t[0].ch[i]);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			int fail=t[u].fail,v=t[u].ch[i];
            if(!v) continue;
			if(!t[fail].ch[i]){t[v].fail=t[fail].ch[i];continue;};
			t[v].fail=t[fail].ch[i];
			q.push(v);
		}
	}
}
int query(char s[]){
	int l=strlen(s),ans=0,p=0;
	for(int i=0;i<l;i++){
		int c=idx(s[i]);
		while(p&&!t[p].ch[c])	p=t[p].fail;
		p=t[p].ch[c];
		if(t[p].v)  ans+=t[p].v,t[p].v=0;
	}
    return ans;
}
int main(){
	char s[maxn];
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%s",s),insert(s);
	make_fail();
	scanf("%s",s);
	printf("%d",query(s));
	return 0;
}
2022/7/13 11:51
加载中...