uva 1449 - Dominating Patterns

简单的AC自动机;

 #include<cstdio>
#include<cstring>
#include<queue>
#define maxn 150005
using namespace std; struct node
{
int cnt;
int id;
node *a[],*tail;
}no[maxn];
int nonocount;
node *newnode()
{
node *p=no+nonocount++;
p->cnt=;
p->id=-;
memset(p->a,NULL,sizeof p->a);
p->tail=NULL;
return p;
} void build(node *root,char *s,int x)
{
int l=strlen(s);
for(int i=;i<l;i++)
{
int k=s[i]-'a';
if(root->a[k]==NULL)
root->a[k]=newnode();
root=root->a[k];
}
root->cnt++;
root->id=x;
} void gettail(node *root)
{
queue<node*>q;
q.push(root);
while(!q.empty())
{
node *fa=q.front();
q.pop();
for(int i=;i<;i++)
if(fa->a[i]!=NULL)
{
node *tmp=fa->tail;
while(tmp&&!tmp->a[i])tmp=tmp->tail;
if(!tmp)fa->a[i]->tail=root;
else fa->a[i]->tail=tmp->a[i];
q.push(fa->a[i]);
}
}
}
int num[];
void query(node *root,char *s)
{
int l=strlen(s);
node *p=root,*tmp;
for(int i=;i<l;i++)
{
int k=s[i]-'a';
while(!p->a[k]&&p!=root)p=p->tail;
p=p->a[k];
if(!p)p=root;
tmp=p;
while(tmp!=root)
{
if(tmp->cnt>=)
{
if(tmp->id!=-)
num[tmp->id]++;
}
tmp=tmp->tail;
}
}
} char s[],t[][];
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
memset(num,,sizeof num);
nonocount=;
node *p=newnode();
for(int i=;i<n;i++)
{
scanf("%s",t[i]);
build(p,t[i],i);
}
gettail(p);
scanf("%s",s);
query(p,s);
int ans=;
for(int i=;i<n;i++)
ans=max(ans,num[i]);
printf("%d\n",ans);
for(int i=;i<n;i++)
if(ans==num[i])
puts(t[i]);
}
return ;
}
上一篇:SharePoint 2013 App Remote Event Receivers


下一篇:《C# 语言学习笔记》——定义属性