求助
查看原帖
求助
199459
Masna_Kimoyo楼主2021/3/6 20:45
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,C=30;
int ans,T,tot;
int book[N],trie[N][C],next[N];
inline int read()
{
	int x=0;
	bool w=0;
	char c=getchar();
	while(!isdigit(c))
		w|=c=='-',c=getchar();
	while(isdigit(c))
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void Build(string s)
{
	int len=s.length();
	int now=0;
	for(register int i=0;i<len;++i)
	{
		int ch=s[i]-'a';
		if(!trie[now][ch])	
			trie[now][ch]=++tot;
		now=trie[now][ch];		
	}
	++book[now];
}
inline void Get_next()
{
	queue<int> q;
	next[1]=0;
	for(register int i=0;i<=25;++i)
		if(trie[0][i])	q.push(trie[0][i]);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(register int i=0;i<=25;++i)
		{
			if(!trie[now][i])	
				trie[now][i]=trie[next[now]][i];
			else
			{
				q.push(trie[now][i]);
				next[trie[now][i]]=trie[next[now]][i];
			}
		}
	}
}
inline void Query(string s)
{
	int len=s.length(),now=0;
	for(register int i=0;i<len;++i)
	{
		int ch=s[i]-'a';
		now=trie[now][ch];
		for(register int j=now;book[j];j=next[j])
		{
			ans+=book[j];
			book[j]=0;
		}
	}
}
int main()
{
	T=read();
	while(T--)
	{
		string s;
		cin>>s;
		Build(s);
	}
	string s;
	cin>>s;
	Query(s);
	printf("%d",ans);
	return 0;
}

虽然我知道这种稍微复杂一点的代码基本上没人会认真看,但还是发一下吧 要是真的有人看呢

2021/3/6 20:45
加载中...