50分求调
查看原帖
50分求调
428449
Amon_Xolotl楼主2023/7/18 18:53
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
int ch[N][28],sum;
int f[N],val[N],last[N],cnt[N],k[N];
int sz;
char t[N];
int idx(char x)
{
	return x-'a';
}
void insert(char* s,int v)
{
	int len=strlen(s);
	int u=0;
	for(int i=0;i<len;++i)
	{
		int c=idx(s[i]);
		if(!ch[u][c])
		{
			++sz;
			val[sz]=0;
			ch[u][c]=sz;
		}
		u=ch[u][c];
	}
	if(val[sz])
	{
		++k[val[sz]];
    }
    else
    {
    	k[v]=1;
    	val[sz]=v;
	}
	
}
void aho()
{
	queue<int> q;
	f[0]=0;
	for(int i=0;i<26;++i)
	{
		int u=ch[0][i];
		if(u)
		{
			q.push(u);
			f[u]=0;
			last[u]=0;
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;++i)
		{
			int c=ch[u][i];
			if(!c)
			{
				ch[u][i]=ch[f[u]][i];
				continue;
			}
			q.push(c);
			int v=f[u];
			while(v&&!ch[v][i])
			{
				v=f[v];
			}
			f[c]=ch[v][i];
			last[c]=val[f[c]]?f[c]:last[f[c]];
		}
	}
}
void print(int j)
{
	if(j)
	{
		++cnt[val[j]];
	    print(last[j]);
	}

}
void corasik(char* t)
{
	aho();
	int len=strlen(t);
	int j=0;
	for(int i=0;i<len;++i)
	{
		int c=idx(t[i]);
		j=ch[j][c];
		if(val[j])
		{
			print(j);
		}
		else if(last[j])
		{
			print(last[j]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	ch[0][0]=0,val[0]=0;
	for(int i=1;i<=n;++i)
	{
		char a[N];
		cin>>a;
		insert(a,i);
	}
	cin>>t;
	corasik(t);
	sum=0;
	for(int i=1;i<=n;++i)
	{
		if(cnt[i])
		{
			sum+=k[i];
		}
	}
	cout<<sum;
	return 0;
}
2023/7/18 18:53
加载中...