程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 2896 病毒侵襲 AC自動機 基礎題

hdu 2896 病毒侵襲 AC自動機 基礎題

編輯:C++入門知識

病毒侵襲
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7381    Accepted Submission(s): 1935

 

Problem Description
當太陽的光輝逐漸被月亮遮蔽,世界失去了光明,大地迎來最黑暗的時刻。。。。在這樣的時刻,人們卻異常興奮——我們能在有生之年看到500年一遇的世界奇觀,那是多麼幸福的事兒啊~~
但網路上總有那麼些網站,開始借著民眾的好奇心,打著介紹日食的旗號,大肆傳播病毒。小t不幸成為受害者之一。小t如此生氣,他決定要把世界上所有帶病毒的網站都找出來。當然,誰都知道這是不可能的。小t卻執意要完成這不能的任務,他說:“子子孫孫無窮匮也!”(愚公後繼有人了)。
萬事開頭難,小t收集了好多病毒的特征碼,又收集了一批詭異網站的源碼,他想知道這些網站中哪些是有病毒的,又是帶了怎樣的病毒呢?順便還想知道他到底收集了多少帶病毒的網站。這時候他卻不知道何從下手了。所以想請大家幫幫忙。小t又是個急性子哦,所以解決問題越快越好哦~~

 


Input
第一行,一個整數N(1<=N<=500),表示病毒特征碼的個數。
接下來N行,每行表示一個病毒特征碼,特征碼字符串長度在20—200之間。
每個病毒都有一個編號,依此為1—N。
不同編號的病毒特征碼不會相同。
在這之後一行,有一個整數M(1<=M<=1000),表示網站數。
接下來M行,每行表示一個網站源碼,源碼字符串長度在7000—10000之間。
每個網站都有一個編號,依此為1—M。
以上字符串中字符都是ASCII碼可見字符(不包括回車)。

 


Output
依次按如下格式輸出按網站編號從小到大輸出,帶病毒的網站編號和包含病毒編號,每行一個含毒網站信息。
web 網站編號: 病毒編號 病毒編號 …
冒號後有一個空格,病毒編號按從小到大排列,兩個病毒編號之間用一個空格隔開,如果一個網站包含病毒,病毒數不會超過3個。
最後一行輸出統計信息,如下格式
total: 帶病毒網站數
冒號後有一個空格。

 


Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc


Sample Output
web 1: 1 2 3
total: 1


Source
2009 Multi-University Training Contest 10 - Host by NIT
 


Recommend
gaojie
 
 
本題 基本上是一個模板題目   , 只要修改一下query()函數     讓裡面的while循環不去標記已經走過的點即可
 
[cpp]
#include<stdio.h>  
#include<string.h>  
#include<malloc.h>  
#include<queue>  
using namespace std; 
int ans[1111][5]; 
char str[1111111]; 
#define  cc 130  
int id,vis[1111],a[1111]; 
struct node 

    int count; 
    struct node *next[cc]; 
    struct node *fail; 
    void init() 
    { 
        int i; 
        for(i=0;i<cc;i++) 
            next[i]=NULL; 
        count=0; 
        fail=NULL; 
    } 
}*root; 
void insert() 

    int len,k; 
    node *p=root; 
    len=strlen(str); 
    for(k=0;k<len;k++) 
    { 
        int pos=str[k]-31; 
        if(p->next[pos]==NULL) 
        { 
            p->next[pos]=new node; 
            p->next[pos]->init(); 
            p=p->next[pos]; 
        } 
        else  p=p->next[pos]; 
    } 
    p->count=id; 

 
void getfail() 

    int i; 
    node *p,*temp,*son; 
    queue<struct node *>que; 
    que.push(root); 
    p=root; 
    while(!que.empty()) 
    { 
        temp=que.front(); 
        que.pop(); 
        for(i=0;i<cc;i++) 
        { 
            son=temp->next[i]; 
            if(son!=NULL) 
            { 
                if(temp==root) 
                { 
                    son->fail=root; 
                } 
                else 
                { 
                    p=temp->fail; 
                    while(p) 
                    { 
                        if(p->next[i]!=NULL) 
                        { 
                            son->fail=p->next[i];///  
                            break; 
                        } 
                        //else  注意這裡沒有else  
                            p=p->fail; 
                    } 
                    if(p==NULL)  son->fail=root; 
                } 
                que.push(son); 
            }    
        } 
          } 

 
void query() 

    int len,i,cnt=0,pos; 
    len=strlen(str); 
    node *p,*temp; 
    p=root; 
    for(i=0;i<len;i++) 
    { 
        pos=str[i]-31; 
        while(!p->next[pos]&&p!=root)  p=p->fail; 
        p=p->next[pos]; 
        if(!p) p=root; 
        temp=p; 
        while(temp!=root)//只要修改下這裡即可  
        { 
            if(temp->count>=1&&!vis[temp->count]) 
            { 
                ans[id][cnt++]=temp->count; 
                vis[temp->count]=1; 
            } 
            temp=temp->fail; 
        } 
    } 

int main() 

    int n,m,i,j; 
    while(scanf("%d",&n)!=EOF) 
    { 
        root= new node; 
        root->fail=NULL; 
        root->init(); 
        getchar(); 
        for(i=1;i<=n;i++) 
        { 
            gets(str); 
            id=i; 
            insert(); 
        } 
        getfail(); 
        scanf("%d",&m); 
        getchar(); 
        memset(ans,0,sizeof(ans)); 
        for(i=1;i<=m;i++) 
        { 
            memset(vis,0,sizeof(vis)); 
            id=i; 
            gets(str); 
            query(); 
        } 
        int cnt=0; 
        for(i=1;i<=m;i++) 
        { 
            if(ans[i][0]>=1) 
            { 
                cnt++; 
                printf("web %d:",i); 
                int a[1111]; 
                memset(a,0,sizeof(a)); 
                for(j=0;ans[i][j]>=1;j++) 
                { 
                    a[ans[i][j]]=1; 
                } 
                int k; 
                for(k=1;k<1100;k++) 
                { 
                    if(a[k]) 
                       printf(" %d",k); 
                } 
                printf("\n"); 
            } 
        } 
        printf("total: %d\n",cnt); 
    } 
    return 0; 
     

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<queue>
using namespace std;
int ans[1111][5];
char str[1111111];
#define  cc 130
int id,vis[1111],a[1111];
struct node
{
 int count;
 struct node *next[cc];
 struct node *fail;
 void init()
 {
  int i;
  for(i=0;i<cc;i++)
   next[i]=NULL;
  count=0;
  fail=NULL;
 }
}*root;
void insert()
{
 int len,k;
 node *p=root;
 len=strlen(str);
 for(k=0;k<len;k++)
 {
  int pos=str[k]-31;
  if(p->next[pos]==NULL)
  {
   p->next[pos]=new node;
   p->next[pos]->init();
   p=p->next[pos];
  }
  else  p=p->next[pos];
 }
 p->count=id;
}

void getfail()
{
 int i;
 node *p,*temp,*son;
 queue<struct node *>que;
 que.push(root);
 p=root;
 while(!que.empty())
 {
  temp=que.front();
  que.pop();
  for(i=0;i<cc;i++)
  {
   son=temp->next[i];
   if(son!=NULL)
   {
    if(temp==root)
    {
     son->fail=root;
    }
    else
    {
     p=temp->fail;
     while(p)
     {
      if(p->next[i]!=NULL)
      {
       son->fail=p->next[i];///
       break;
      }
      //else  注意這裡沒有else
       p=p->fail;
     }
     if(p==NULL)  son->fail=root;
    }
    que.push(son);
   } 
  }
    }
}

void query()
{
 int len,i,cnt=0,pos;
 len=strlen(str);
 node *p,*temp;
 p=root;
 for(i=0;i<len;i++)
 {
  pos=str[i]-31;
  while(!p->next[pos]&&p!=root)  p=p->fail;
  p=p->next[pos];
  if(!p) p=root;
  temp=p;
  while(temp!=root)//只要修改下這裡即可
  {
   if(temp->count>=1&&!vis[temp->count])
   {
    ans[id][cnt++]=temp->count;
    vis[temp->count]=1;
   }
   temp=temp->fail;
  }
 }
}
int main()
{
 int n,m,i,j;
 while(scanf("%d",&n)!=EOF)
 {
  root= new node;
  root->fail=NULL;
  root->init();
  getchar();
  for(i=1;i<=n;i++)
  {
   gets(str);
   id=i;
   insert();
  }
  getfail();
  scanf("%d",&m);
  getchar();
  memset(ans,0,sizeof(ans));
  for(i=1;i<=m;i++)
  {
   memset(vis,0,sizeof(vis));
   id=i;
   gets(str);
   query();
  }
  int cnt=0;
  for(i=1;i<=m;i++)
  {
   if(ans[i][0]>=1)
   {
    cnt++;
    printf("web %d:",i);
    int a[1111];
    memset(a,0,sizeof(a));
    for(j=0;ans[i][j]>=1;j++)
    {
     a[ans[i][j]]=1;
    }
    int k;
    for(k=1;k<1100;k++)
    {
     if(a[k])
        printf(" %d",k);
    }
    printf("\n");
   }
  }
  printf("total: %d\n",cnt);
 }
 return 0;
 
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved