「ZOJ-3430」Detect the Virus (AC自动机)

发表于 | 分类于 ，

「ZOJ-3430」Detect the Virus
AC自动机，求每个匹配串能匹配的模式串种类数

题意

给定$n$个模式串和$m$个匹配串(均以base64加密)，求匹配串中出现模式串的种类个数。

解法

对于base64的解码，即将字符对应的6位二进制串转化为8位二进制数，可以通过位运算完成，如下：

1
2
3
4
5
6
7
//取编码后字符串当前位的二进制串，置于后6位
len+=6,x=(x<<6)|base64[encode[i]];	
if(len>=8) {
    //取x的前8位，即为解码后的字符
	decode[p++] = (x >> (len - 8)) & 0xff;		
	len -= 8;
}

理论上解码之后就可以当做AC自动机模板题做然而

  • Segmentation Fault ：解码之后的字符串范围在0-256，需要使用unsigned char，否则会导致数组下标小于零越界(其实int也可以）;
  • Wrong Answer：解码后的字符串值包含0，不能直接使用strlen(str)求解字符串长度；
  • Wrong Answer：求解的是字符串的种类数

好了我就这么被卡了5小时。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

static const char b64[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
const int maxn=50000+10;

map<char,int> mp;

int n;
unsigned char str[5000+10],enstr[5000+10];

int decode()
{
    int len=0,x=0,p=0;
    for(int i=0;enstr[i]&&enstr[i]!='=';i++)
    {
        len+=6,x=(x<<6)|mp[enstr[i]];
        if(len>=8) {
            str[p++] = (x >> (len - 8)) & 0xff;
            len -= 8;
        }
    }
    return p;
}

class ACAutomation
{
public:
    int nex[maxn][256],fail[maxn],en[maxn],vis[maxn];
    int root,L;
    int newnode()
    {
        for(int i=0;i<256;i++)
            nex[L][i]=-1;
        en[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void insert(unsigned char buf[],int len,int key)
    {
        int now=root;
        for(int i=0;i<len;i++)
        {
            if(nex[now][buf[i]]==-1)
                nex[now][buf[i]]=newnode();
            now=nex[now][buf[i]];
        }
        en[now]=key;
    }
    void build()
    {
        queue<int> Q;
        fail[root]=root;
        for(int i=0;i<256;i++)
            if(nex[root][i]==-1)
                nex[root][i]=root;
            else
            {
                fail[nex[root][i]]=root;
                Q.push(nex[root][i]);
            }
        while(!Q.empty())
        {
            int now=Q.front();
            Q.pop();
            for(int i=0;i<256;i++)
                if(nex[now][i]==-1)
                    nex[now][i]=nex[fail[now]][i];
                else
                {
                    fail[nex[now][i]]=nex[fail[now]][i];
                    Q.push(nex[now][i]);
                }
        }
    }
    int query(unsigned char buf[],int len)
    {
        int now=root;
        int res=0;
        memset(vis,0,sizeof vis);
        for(int i=0;i<len;i++)
        {
            now=nex[now][buf[i]];
            int tmp=now;
            while(tmp!=root)
            {
                if(en[tmp]) vis[en[tmp]]=true;
                tmp=fail[tmp];
            }
        }
        for(int i=1;i<=n;i++) if(vis[i]) res++;
        return res;
    }
}AC;

int main()
{
    for(int i=0;i<64;i++) mp[b64[i]]=i;
    int m,len;
    while(scanf("%d",&n)!=EOF)
    {
        AC.init();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",enstr);
            len=decode();
            AC.insert(str,len,i);
        }
        AC.build();
        scanf("%d",&m);
        while(m--)
        {
            scanf("%s",enstr);
            len=decode();
            printf("%d\n",AC.query(str,len));
        }
        printf("\n");
    }
    return 0;
}