首页 > 其他 > 详细

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

时间:2014-08-05 18:39:50      阅读:288      评论:0      收藏:0      [点我收藏+]

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)进行排序好就可以输出了

总代码如下:

bubuko.com,布布扣
 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

 

bubuko.com,布布扣
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <string>
using namespace std;
#define N 1000*52
char 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

 

bubuko.com,布布扣
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <string>
using namespace std;
#define N 1000*52
char 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

 

病毒的侵扰和再侵扰两道AC自动机的应用,布布扣,bubuko.com

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

原文:http://www.cnblogs.com/CSU3901130321/p/3892620.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!