UVA1449 Dominating Patterns 题解

UVA1449 Dominating Patterns 题解

板子题诶。

解法

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

在查找时，每次都暴力的条 $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 200int 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;
}