Menu
Article ACM

ZOJ 3430 Detect the Virus

NodeKey

NodeKey

• 3 min read

其实是道板子题…………

但是AC自动机已经学会很长时间了，当学会之后一看发现高阶的应用都得和DP相结合，还有矩阵加速呀什么什么的……就没再去碰过了

结果昨天的多校的一道中等题就是AC自动机+状压……

有点崩溃，至今的我还是基本上只会板子……所以今天在状压写累的时候开始写一下AC自动机。

顺便小小的总结一下AC自动机模板的用法和需要注意的地方。

  1. 数组大小的上限与Trie相关，上限为插入字符总数 一开始我还以为是查询字符长度
  2. 如果数组下标从0开始，end对数组标记需初始化为 -1 ，一般建议全初始化为 -1
  3. 格外小心字符范围，一般字母26，可见字符128，而这题的范围就是 256 因为 (2^8 )

题意：
还是有点老套的题意。简单说就是让你找出一个网站上的病毒数量，这跟之前很多模板题是一样的……
略有不同的是这些病毒都是经过加密的，再简单说，这个加密方式只是确定的进制转化，原本是8进制的密码，现在给你6进制形式。

思路：
只要把病毒给解码出来，就是一个模板题。
当然方法各有不同，我感觉我写的略有麻烦，建议去看kuangbin的转化。

不过A了我就不想管了

注意输出格式

#include <bits/stdc++.h>

using namespace std;

const int max_n = 520 * 64;
const int max_c = 256;

char buf[4050];
unsigned char kao[4050];
int n;

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = -1;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    inline void insert(unsigned char str[], int len, int id)
    {
        int now = root;
        for (int i = 0; i < len; i++) {
            int c = str[i];
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = id;
    }

    inline void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    bool used[520];
    int query(unsigned char str[], int len)
    {
        fill(used, used + n, false);
        int now = root, res = 0;
        for (int i = 0; i < len; i++) {
            now = next[now][(int)str[i]];
            int cur = now;
            while (cur != root) {
                if (end[cur] != -1)
                    used[end[cur]] = true;
                cur = fail[cur];
            }
        }
        for (int i = 0; i < n; i++)
            if (used[i])
                res++;
        return res;
    }
} aho;

int getNum(char c)
{
    if (c >= 'a' && c <= 'z')
        return c - 'a' + 26;
    if (c >= 'A' && c <= 'Z')
        return c - 'A';
    if (c >= '0' && c <= '9')
        return c - '0' + 52;
    if (c == '+')
        return 62;
    return 63;
}

void change(char from[], unsigned char to[], int& an)
{
    int len = strlen(from), num = 7, key = 0;
    an = 0;
    while (from[len - 1] == '=')
        len--;
    for (int i = 0; i < len; i++) {
        int c = getNum(from[i]);
        for (int j = 5; j >= 0; j--) {
            if (c & 1 << j)
                key += (1 << num);
            num--;
            if (num == -1) {
                to[an++] = key;
                key = 0, num = 7;
            }
        }
    }
    to[an] = '\0';
}

int main()
{
    int m, len;
    while (scanf("%d", &n) != EOF) {
        aho.init();
        for (int i = 0; i < n; i++) {
            scanf("%s", buf);
            change(buf, kao, len);
            aho.insert(kao, len, i);
        }
        aho.build();
        scanf("%d", &m);
        while (m--) {
            scanf("%s", buf);
            change(buf, kao, len);
            printf("%d\n", aho.query(kao, len));
        }
        puts("");
    }
    return 0;
}
Share