其实是道板子题…………

但是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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

AC自动机

HDU 6138 Fleet of the Eternal Throne

昨天多校的AC自动机入门题…… 为什么我还要写AC自动机入门题呢,因为 Read more…

AC自动机

HDU 6096 String

AC自动机好题,恐怕出题人都完全没有想到是AC自动机。 队友在写这题的 Read more…

AC自动机

HDU 2457 DNA repair

好题。但kuangbin说这道题已经是很简单的DP了。 首先kuang Read more…