首页 > 代码库 > 病毒的侵扰和再侵扰两道AC自动机的应用

病毒的侵扰和再侵扰两道AC自动机的应用

2024-07-15 22:28:56   220人阅读

HDU2896 病毒的侵扰

http://vjudge.net/problem/viewProblem.action?id=16404

题目大意：

记录每个病毒的编号，并给出一些网站的源码，分别输出网站及其对应编号中所含病毒的编号，没有就不输出

最后输出有病毒网站的个数

 

这道题需要注意的是这个所有ASCII码均会用到，所以我之前傻傻地写str[i]-‘a‘还不知为什么会错简直苦逼~~

这里直接用ch[now][str[i]]找到对应位置即可

因为要记录编号，为了防止重复访问，我对query中进行了一个visit[]数组访问进行判断的操作

query函数如下：

 1  void query(char *str){ 2         int len=strlen(str); 3         int now=root,ret=0; 4         for(int i=0;i<len;i++){ 5             now=ch[now][str[i]]; 6             int k=now; 7             while(k!=root&&(!visit[k]&&val[k])){//这是要循环到找到fail值为root的时候或者找到匹配的字符串的时候，否则一直向前找fail值， 8                 if(!visit[k])sum++,ans[ret++]=val[k],visit[k]=1; 9                 k=last[k];10             }11         }12     }

用ans[]记录所有编号，sum记录病毒个数，那么就可以在main函数进行sort(ans,ans+sum)进行排序好就可以输出了

总代码如下：

 1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 #define N 500*201 7 char str[10005]; 8 int ans[505],visit[N],sum; 9 struct AC{10     int ch[N][128],fail[N],val[N],last[N],tmp,root,cnt;11     int newnode(){12         val[tmp]=0;13         memset(ch[tmp],0,sizeof(ch[tmp]));14         return tmp++;15     }16     void init(){17         tmp=0,cnt=0;18         root=newnode();19     }20     void add(char *s){21         int len=strlen(s);22         int now=root;23         for(int i=0;i<len;i++){24             int &k=ch[now][s[i]];25             if(!k) k=newnode();26             now=k;27         }28         cnt++;29         val[now]=cnt;30     }31     void get_fail(){32         fail[root]=root;33         queue<int> q;34         for(int i=0;i<128;i++){35             int v=ch[root][i];36             if(v)37                 fail[v]=last[v]=0,q.push(v);38         }39         while(!q.empty()){40             int now=q.front();41             q.pop();42             for(int i=0;i<128;i++){43                 int v=ch[now][i];44                 if(!v) ch[now][i]=ch[fail[now]][i];45                 else{46                     fail[v]=ch[fail[now]][i];47                     last[v]=val[fail[v]]?fail[v]:last[fail[v]];48                     q.push(v);49                 }50             }51         }52     }53     void query(char *str){54         int len=strlen(str);55         int now=root,ret=0;56         for(int i=0;i<len;i++){57             now=ch[now][str[i]];58             int k=now;59             while(k!=root&&(!visit[k]&&val[k])){//这是要循环到找到fail值为root的时候或者找到匹配的字符串的时候，否则一直向前找fail值，60                 if(!visit[k])sum++,ans[ret++]=val[k],visit[k]=1;61                 k=last[k];62             }63         }64     }65 }ac;66 int main()67 {68     int n,m;69     while(scanf("%d",&n)!=EOF){70         memset(ans,0,sizeof(ans));71         ac.init();72         for(int i=0;i<n;i++){73             scanf("%s",str);74             ac.add(str);75         }76         ac.get_fail();77         scanf("%d",&m);78         int c=0;79         for(int i=1;i<=m;i++){80             sum=0;81             scanf("%s",str);82             memset(visit,0,sizeof(visit));83             ac.query(str);84             sort(ans,ans+sum);85             if(sum>0){86                 printf("web %d:",i);87                 for(int j=0;j<sum;j++) printf(" %d",ans[j]);88                 printf("\n");89                 c++;90             }91         }92         printf("total: %d\n",c);93     }94     return 0;95 }
View Code


HDU 3065病毒再侵扰

http://vjudge.net/problem/viewProblem.action?id=16405

给一堆带序号的病毒，再给一个网站源码，问这个网站有哪些病毒，分别有几个，输出病毒码和其对应的个数

这里的query主串中因为会重复模式串，所以不能将val[]数组进行清零，要让他每次都能访问到

 1 void query(char *str){ 2         int len=strlen(str); 3         int now=root; 4         for(int i=0;i<len;i++){ 5             now=ch[now][str[i]]; 6             int k=now; 7             while(k!=root){//这是要循环到找到fail值为root的时候或者找到匹配的字符串的时候，否则一直向前找fail值， 8                 if(val[k]>0) ans[val[k]]++; 9                 k=last[k];10             }11         }12     }

这道题和上一道字符串有所区别，这里病毒码只有26个大写字母，主串可以是128个ASCII码的任何字符

当然直接在AC结构体中定义ch[N][128]也并未超内存

这是我最开始写的代码:

Memory: 16756 KB Time: 296 MS
Language: G++ 

Result: Accepted

 

#include <cstdio>#include <cstring>#include <queue>#include <iostream>#include <string>using namespace std;#define N 1000*52char str[2000010];int ans[1001];struct AC{    int ch[N][128],fail[N],val[N],last[N],tmp,root;    int newnode(){        val[tmp]=0;        memset(ch[tmp],0,sizeof(ch[tmp]));        return tmp++;    }    void init(){        tmp=0;        root=newnode();    }    void add(string s,int cnt){        int len=s.length();        int now=root;        for(int i=0;i<len;i++){            int &k=ch[now][s.at(i)];            if(!k) k=newnode();            now=k;        }        val[now]=cnt;    }    void get_fail(){        fail[root]=root;        queue<int> q;        for(int i=0;i<128;i++){            int v=ch[root][i];            if(v)                fail[v]=last[v]=0,q.push(v);        }        while(!q.empty()){            int now=q.front();            q.pop();            for(int i=0;i<128;i++){                int v=ch[now][i];                if(!v) ch[now][i]=ch[fail[now]][i];                else{                    fail[v]=ch[fail[now]][i];                    last[v]=val[fail[v]]?fail[v]:last[fail[v]];                    q.push(v);                }            }        }    }    void query(char *str){        int len=strlen(str);        int now=root;        for(int i=0;i<len;i++){            now=ch[now][str[i]];            int k=now;            while(k!=root){//这是要循环到找到fail值为root的时候或者找到匹配的字符串的时候，否则一直向前找fail值，                if(val[k]>0) ans[val[k]]++;                k=last[k];            }        }    }}ac;int main(){    int n;    string s[1001];    while(scanf("%d",&n)!=EOF){        memset(ans,0,sizeof(ans));        ac.init();        for(int i=0;i<n;i++){            cin>>s[i+1];            ac.add(s[i+1],i+1);        }        ac.get_fail();        scanf("%s",str);        ac.query(str);        for(int i=1;i<=1000;i++){            if(ans[i]>0) cout<<s[i]<<": "<<ans[i]<<endl;        }    }    return 0;}
View Code

但是我们定义一个ch[N][26]的数组却可以减少更多的内存占用，那么我们每次找位置都是用now=ch[now][str[i]-‘A‘]来进行操作
在query中面对不在A~Z范围内的数，我们就利用一个if判断条件来做

if(str[i]<‘A‘||str[i]>‘Z‘) now=root;//因为不在A~Z范围内的数是不存在有字母能跟它进行匹配的，所以直接将指针移回根节点重新进行判断

else{

}

Memory: 5584 KB Time: 187 MS
Language: G++ Result: Accepted

 

#include <cstdio>#include <cstring>#include <queue>#include <iostream>#include <string>using namespace std;#define N 1000*52char str[2000010];int ans[1001];struct AC{    int ch[N][26],fail[N],val[N],last[N],tmp,root;    int newnode(){        val[tmp]=0;        memset(ch[tmp],0,sizeof(ch[tmp]));        return tmp++;    }    void init(){        tmp=0;        root=newnode();    }    void add(string s,int cnt){        int len=s.length();        int now=root;        for(int i=0;i<len;i++){            int &k=ch[now][s.at(i)-‘A‘];            if(!k) k=newnode();            now=k;        }        val[now]=cnt;    }    void get_fail(){        fail[root]=root;        queue<int> q;        for(int i=0;i<26;i++){            int v=ch[root][i];            if(v)                fail[v]=last[v]=0,q.push(v);        }        while(!q.empty()){            int now=q.front();            q.pop();            for(int i=0;i<26;i++){                int v=ch[now][i];                if(!v) ch[now][i]=ch[fail[now]][i];                else{                    fail[v]=ch[fail[now]][i];                    last[v]=val[fail[v]]?fail[v]:last[fail[v]];                    q.push(v);                }            }        }    }    void query(char *str){        int len=strlen(str);        int now=root;        for(int i=0;i<len;i++){            if(str[i]>‘Z‘||str[i]<‘A‘) now=root;            else{                now=ch[now][str[i]-‘A‘];                int k=now;                while(k!=root){//这是要循环到找到fail值为root的时候或者找到匹配的字符串的时候，否则一直向前找fail值，                    if(val[k]>0) ans[val[k]]++;                    k=last[k];                }            }        }    }}ac;int main(){    int n;    string s[1001];    while(scanf("%d",&n)!=EOF){        memset(ans,0,sizeof(ans));        ac.init();        for(int i=0;i<n;i++){            cin>>s[i+1];            ac.add(s[i+1],i+1);        }        ac.get_fail();        scanf("%s",str);        ac.query(str);        for(int i=1;i<=1000;i++){            if(ans[i]>0) cout<<s[i]<<": "<<ans[i]<<endl;        }    }    return 0;}
View Code

 


联系
我们