求助debug
查看原帖
求助debug
261018
封禁用户楼主2020/4/27 12:12
#define mod 10
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#define kkk register
#define ll long long
#define inf 2147098934832ll
using namespace std;
int read(){int ans=0,f=1;char a=getchar();while(a>'9'||a<'0')f|=a=='-',a=getchar();while(a>='0'&&a<='9')ans=(ans<<3)+(ans<<1)+a-'0',a=getchar();return ans*f;}
//一条long long的黄金分割线-----------------------------------------------------------------------------------------------------------------------------------
int n,cnt=1,num=1;
string s;
struct node{
	node *fail;
	node *trie[27];
	int end=0;
	int cnt=0;
}*root=new node(),*now,*v,*fafail;
queue<node*>q;
void add(string s){
	now=root;root->cnt=1;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		if(now->trie[c]==NULL)now->trie[c]=new node(),now->trie[c]->cnt=++num;
		now=now->trie[c];
	}
	++now->end;
}
void buildfail(){
	for(int i=0;i<=25;i++)if(root->trie[i]!=NULL)q.push(root->trie[i]),root->trie[i]->fail=root;
	while(!q.empty()){
		now=q.front();q.pop();
		for(int i=0;i<=25;i++){
			v=now->trie[i];
			if(v){
				q.push(v);fafail=now->fail;
				while(fafail&&fafail->trie[i])fafail=fafail->fail;
				if(fafail==NULL)v->fail=root;
				else v->fail=fafail->trie[i];
				if(v->fail->end)v->end+=v->fail->end;
			}
		}
	}
}
int query(){
	int ans=0;
	now=root;
	for(int i=0;i<s.size();i++){
		int c=s[i]-'a';
		while(now->trie[c]==NULL&&now->fail)
			now=now->fail;
		if(now->trie[c])now=now->trie[c];
		else continue;
		if(now->end)ans+=now->end,now=now->fail;
	}
	return ans;
}
int main(){
	root=new node();
	n=read();
	for(int i=1;i<=n;i++)cin>>s,add(s);
	buildfail();
	cin>>s;
	cout<<query();
	return 0;
}
2020/4/27 12:12
加载中...