题解 P2444 【[POI2000]病毒】

小越越 · 2018-08-11 14:12:49 · 题解

题意：

求一个无限长的串，不包含给定的模式串。

思路：

看起来像是字符串匹配的题。很容易想到不符合要求的串就是包含给定模式串的串。也就是说，要是不符合要求的串放在ac自动机上跑一下，就会搜到是带有模式串结尾标记的节点（更确切地说是：在fail树上到根节点路径上有结尾标记的节点）。

那么要求一个不包含模式串的无限长的串，只要在ac自动机上dfs一遍，不走在fail树上到根节点路径上有结尾标记的节点（这句话有点长），如果产生环就可以无限走下去了，反之如果没有环就是NIE。

代码：

几乎就是个板子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<cstdlib>
using namespace std;
const int N = 3e4+10;
struct TRIE{
    int son[2], fail;
    bool isend;
}trie[N];
int n, tot;
string s;
bool vis[N];

void Insert(string s)//TRIE板子
{
    int len = s.size(), now = 0, val;
    for (int i = 0; i < len; i++){
        val = s[i]-'0';
        if (trie[now].son[val] == 0)
            trie[now].son[val] = ++tot;
        now = trie[now].son[val];
    }
    trie[now].isend = 1;
}

void Build()//AC自动机板子
{
    queue<int> q;
    for (int i = 0; i < 2; i++)
        if (trie[0].son[i])
            q.push(trie[0].son[i]);
    while (!q.empty()){
        int fa = q.front();
        q.pop();
        for (int i = 0; i < 2; i++){
            int &now = trie[fa].son[i];
            if (now){
                trie[now].fail = trie[trie[fa].fail].son[i];
                trie[now].isend |= trie[trie[trie[fa].fail].son[i]].isend;
                //以上那句话很重要，因为能走某个节点的条件是fail树上他到根的路径上没有尾标记，所以必须把fail父亲的状态继承下来
                q.push(now);
            }
            else
                now = trie[trie[fa].fail].son[i];
        }
    }
}

void Dfs(int now)//普通的DFS
{
    if (vis[now]){
        cout << "TAK";
        exit(0);
    }
    vis[now] = true;
    for (int i = 0; i < 2; i++){
        int nxt = trie[now].son[i];
        if (trie[nxt].isend) continue;
        Dfs(nxt);
    }
    vis[now] = false;
}

int main()
{
    cin >> n;
    tot = 0;
    memset(trie, 0, sizeof(trie));
    while (n--){
        cin >> s;
        Insert(s);
    }
    Build();
    Dfs(0);
    cout << "NIE";
    return 0;
}