UVA1449 Dominating Patterns 题解

UVA1449 Dominating Patterns 题解

板子题诶。

解法

AC 自动机模板题，因为数据范围比较小，所以不加拓扑排序优化建图即可通过本题。这里简单介绍一下拓扑排序优化建图。

在查找时，每次都暴力的条 f a i l fail fail 指针是很消耗时间的，查找到了一个字符串可能意味着找到了多个字符串，例如我们有两个模式串 bc 和 abc，我们找到了串 abc，这同时意味着我们找到了串 bc，如果每次都去跳失配边的话效率过低，我们可以在找到一个模式串后打标记，最后进行拓扑排序求得最后的答案。

为什么可以使用拓扑排序？

因为失配边都是有向边，而失配边的起点一定比终点深度要深，而且不会存在自环。所以所有失配边所构成的图是一个有向无环图。

另外，这里建图不用真的把边都建出来，统计一下入度就行。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
	/**
	 * 快读快写。
	*/
};
using namespace fast_IO;
class AC_auto
{
private:
	#define LEN 1000001
	#define N 200
	int a[LEN][26],val[LEN],flag[LEN],fail[LEN],ind[LEN],cnt,tmp;
	int ans[N],map[N];
	std::deque<int> q;
public:
	inline AC_auto()
	{
		memset(fail,0,sizeof(fail)),memset(val,0,sizeof(val)),memset(flag,0,sizeof(flag));
		memset(a,0,sizeof(a)),memset(ind,0,sizeof(ind));
		memset(ans,0,sizeof(ans)),memset(map,0,sizeof(map));
		cnt=1;
	}
	inline void clear()
	{
		for(int i=0;i<=cnt;i++) memset(a[i],0,sizeof(a[i])),val[i]=flag[i]=fail[i]=ind[i]=0;
		memset(ans,0,sizeof(ans)),memset(map,0,sizeof(map));
		cnt=1;
	}
	inline void build()
	{
		for(int i=0;i<26;i++) a[0][i]=1;
		q.push_back(1);
		while(!q.empty())
		{
			tmp=q.front();q.pop_front();
			for(int i=0;i<26;i++)
				if(a[tmp][i])
					fail[a[tmp][i]]=a[fail[tmp]][i],ind[fail[a[tmp][i]]]++,q.push_back(a[tmp][i]);
			else a[tmp][i]=a[fail[tmp]][i];
		}
	}
	inline void add(std::string st,int pos)
	{
		int now=1;
		for(int i=0;i<st.size();i++)
		{
			if(!a[now][st[i]-'a']) a[now][st[i]-'a']=++cnt;
			now=a[now][st[i]-'a'];
		}
		if(!flag[now]) flag[now]=pos;
		map[pos]=flag[now];
	}
	inline void ask(std::string st)
	{
		int now=1;
		for(int i=0;i<st.size();i++) now=a[now][st[i]-'a'],val[now]++;
	}
	inline void topo_sort()
	{
		for(int i=1;i<=cnt;i++) if(!ind[i]) q.push_back(i);
		while(!q.empty())
		{
			tmp=q.front(),q.pop_front();
			ans[flag[tmp]]=val[tmp],val[fail[tmp]]+=val[tmp];
			if(!(--ind[fail[tmp]])) q.push_back(fail[tmp]);
		}
	}
	inline std::vector<int> output(const int l,const int r)
	{
		std::vector<int> ret;
		int maxi=0;
		for(int i=l;i<=r;i++)
			if(ans[map[i]]>maxi) maxi=ans[map[i]],ret.clear(),ret.push_back(i);
			else if(ans[map[i]]==maxi) ret.push_back(i);
		out<<maxi<<'\n';
		return ret;
	}
};
AC_auto ac_auto;
int n;
std::string s,t[200];
std::vector<int> v;
int main()
{
	while(1)
	{
		in>>n;
		if(n==0) break;
		ac_auto.clear();
		for(int i=1;i<=n;i++) in>>t[i],ac_auto.add(t[i],i);
		ac_auto.build(),in>>s,ac_auto.ask(s),ac_auto.topo_sort(),v=ac_auto.output(1,n);
		for(int i=0;i<v.size();i++) out<<t[v[i]]<<'\n';
	}
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}