有无好心人帮我调调板子
查看原帖
有无好心人帮我调调板子
111475
doctorZ_楼主2022/11/21 21:42
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
namespace ac
{
	const int N=1e6+1000;
	int cnt;
	struct Trie
	{
		int son[30],fail,num;
	}t[N+10];
	void insert(string s)
	{
		int len=s.length(),u=0;
		for(int i=0;i<len;i++)
		{
			if(!t[u].son[s[i]-'a']) t[u].son[s[i]-'a']=++cnt;
			u=t[u].son[s[i]-'a'];
		}
		t[u].num++;
	}
	queue<int> q;
	void getfail()
	{
		for(int i=0;i<='z'-'a';i++)
			if(t[0].son[i])
				t[t[0].son[i]].fail=0,q.push(t[0].son[i]);
		for(int u;!q.empty();)
		{
			u=q.front(),q.pop();
			for(int i=0;i<='z'-'a';i++)
			{
				if(t[u].son[i]) t[t[u].son[i]].fail=t[t[u].fail].son[i],q.push(t[u].son[i]);
				else t[u].son[i]=t[t[u].fail].son[i];
			}
		}
	}
	int query(string s)
	{
		int u=0,len=s.length(),ans=0;
		for(int i=0;i<len;i++)
		{
			u=t[i].son[s[i]-'a'];
			int k=u;
			while(k>0&&t[k].num!=-1)
				ans+=t[k].num,t[k].num=-1,k=t[k].fail;
		}
		return ans;
	}
}
int main()
{
	freopen("ac1.in","r",stdin);
	int n;
	scanf("%d",&n);
	string s;
	for(;n--;) cin>>s,ac::insert(s);
	ac::getfail();
	cin>>s;
	printf("%d\n",ac::query(s));
	return 0;
}
2022/11/21 21:42
加载中...