hdu2896 病毒侵袭(AC自动机)
程序员文章站
2022-06-06 20:31:51
...
题目来源:hdu2896 病毒侵袭
完整题目:
注意事项:
①MLE 32768KB卡限,这里用指针的AC自动机卡了32628KB过了,考虑用数组的AC自动机
②病毒小于等于3个也得排序啊
③在线输出和离线输出都可以
AC代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
const int INF=0x3f3f3f3f;
const int mod=10007;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
//ascii码可见 开128数组比较靠谱 扩容 注意26只适用于小写字母的情况
//这题有毒 多组输入没说 稍微开大一点空间就MLE 32768kb异常的坑
struct acnode{
int sum;
int v;//代表是几号串的标号
acnode* next[128];
acnode* fail;
acnode(){
v=0;
for(int i =0;i<128;i++)
next[i]=NULL;
fail= NULL;
sum=0;
}
};
acnode *root;
char s[10005],tmp[205];//搞离线
int ans[15],n,m,final,mark[505];
acnode* newnode()
{
acnode *p = new acnode();
return p;
}
//插入函数
void Insert(char *s,int num)
{
acnode *p = root;
for(int i = 0; s[i]; i++)
{
int x = s[i];
if(p->next[x]==NULL)
{
acnode *nn=newnode();
p->next[x]=nn;
}
p = p->next[x];
}
p->sum++;
p->v=num;
}
//获取fail指针,在插入结束之后使用
void getfail(){
queue<acnode*> q;
for(int i = 0 ; i < 128 ; i ++ )
{
if(root->next[i]!=NULL){
root->next[i]->fail = root;
q.push(root->next[i]);
}
}
while(!q.empty())
{
acnode* tem = q.front();
q.pop();
for(int i = 0;i<128;i++)
{
if(tem->next[i]!=NULL)
{
acnode *p;
if(tem == root)
{
tem->next[i]->fail = root;
}
else
{
p = tem->fail;
while(p!=NULL){
if(p->next[i]!=NULL){
tem->next[i]->fail = p->next[i];
break;
}
p=p->fail;
}
if(p==NULL)
tem->next[i]->fail = root;
}
q.push(tem->next[i]);
}
}
}
}
//匹配函数
int ac_automation(char *ch)
{
acnode *p = root;
int len = strlen(ch),tot=0;
for(int i = 0; i < len; i++)
{
int x = ch[i];
while(p->next[x]==NULL && p != root)//没匹配到,那么就找fail指针。
p = p->fail;
p = p->next[x];
if(!p)
p = root;
acnode *temp = p;
while(temp != root)
{
if(temp->sum >= 0)
{
if(temp->v&&!mark[temp->v])//标记一下不然可能会影响结果 别的失配的时候正好路过该单词尾
{
ans[tot++]=temp->v;
mark[temp->v]=1; //匹配过,不该改为0,不然下次就没法匹配了
}
}
else break;
temp = temp->fail;
}
}
return tot;
}
void Delete(acnode* root)
{
for(int i=0;i<128;++i)if(root->next[i])Delete(root->next[i]);
delete root;
}
void init()
{
mem(ans,0);
final=0;
}
int main()
{
while(~scanf("%d",&n))
{
init();
root=newnode();
sci(n);
rep(i,1,n)
{
scanf("%s",tmp);
Insert(tmp,i);
}
getfail();
sci(m);
rep(i,1,m)
{
scanf("%s",s);
int num=ac_automation(s);
if(num)sort(ans,ans+num);//坑比的排序,忽视了一直wa
rep(j,0,num-1)
{
if(!j)final++,printf("web %d:",i);
printf(" %d",ans[j]);
if(j==num-1)puts("");
}
mem(mark,0);
}
printf("total: %d\n",final);
Delete(root);
}
return 0;
}