P2444:「POI2000」病毒题解

主要思路

这道题铁定是要用 AC 自动机来进行实现的。我们把这些字符串全部通过 insert 操作放入了自动机之后，怎样改写 build_AC_automation 操作来搞定这道题呢？

首先，我们发现 fail 指针可以把整个 trie 树变成一张图（每一个点都加了一条虚边）。所以我们会发现，只要我们找到这张图的一个环，且这个环上所有的点都不是某个不安全代码的结尾点，就可以认定有无限长的代码安全。原因解析起来非常的简单，因为如果有一个这样安全的环，那么无限长的代码势必在这个环内无限循环，且因为这是安全的，所以也可以保证这一长串的代码是安全的。

详见代码。

代码

// P2444.cpp
#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int MX_N = 30020;
struct node
{
    node *nxt[2], *fail;
    bool sum, ins, vis;
    node() { nxt[0] = nxt[1] = fail = NULL, sum = 0, ins = vis = false; }
};
node *root;
int n, longest;
void insert(string str)
{
    int siz = str.length();
    node *p = root;
    for (int i = 0; i < siz; i++)
        p = (p->nxt[str[i] - '0'] == NULL) ? (p->nxt[str[i] - '0'] = new node()) : p->nxt[str[i] - '0'];
    p->sum = true;
}
void build_ac_automation()
{
    queue<node *> q;
    q.push(root);
    while (!q.empty())
    {
        node *curt = q.front();
        q.pop();
        for (int i = 0; i < 2; i++)
            if (curt->nxt[i] != NULL)
            {
                if (curt == root)
                    curt->nxt[i]->fail = root;
                else
                {
                    node *p = curt->fail;
                    while (p)
                        if (p->nxt[i] != NULL)
                        {
                            curt->nxt[i]->fail = p->nxt[i];
                            curt->nxt[i]->sum |= p->nxt[i]->sum;
                            break;
                        }
                        else
                            p = p->fail;
                    if (p == NULL)
                        curt->nxt[i]->fail = root;
                }
                q.push(curt->nxt[i]);
            }
            else if (curt->fail != NULL)
                curt->nxt[i] = curt->fail->nxt[i];
    }
}
bool dfs(node *curt)
{
    if (curt->ins)
        return true;
    if (curt->vis || curt->sum > 0)
        return false;
    curt->vis = curt->ins = true;
    for (int i = 0; i < 2; i++)
        if (curt->nxt[i] != NULL && dfs(curt->nxt[i]))
            return true;
    curt->ins = false;
    return false;
}
char buff[30020];
int main()
{
    scanf("%d", &n);
    root = new node();
    for (int i = 1; i <= n; i++)
        scanf("%s", buff), insert(buff);
    build_ac_automation();
    if (dfs(root))
        printf("TAK");
    else
        printf("NIE");
    return 0;
}