题解 P2444 【[POI2000]病毒】

vani_prcups · 2017-12-15 21:41:31 · 题解

AC自动机

简单的来说，就是构造一个只含0和1的字符串，不能与Trie完成匹配（即包含病毒代码）。我们采用深搜的方式，往构造的字符串中添0或1，如果发现有环（即可以反复添加而不匹配），则存在这样的字符串。如果被逼到无法添加，就不匹配。

这里主要说一个坑点（见注释）：如果Trie在某位置val[i]==1（即完成匹配），那么后面失配到i位置的位置val均为1，否则会WA三个点。

剩下的，交给代码吧。这里ht数组是一个小优化，避免重复搜索，visited判环。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define __ long long
using namespace std;
__ n,ch[60005][3],val[60005],ht[60005],p[60005],visited[60005],len,flag;
__ ls;
queue <__> q;
char s[30005];
void pre()
{
    for (int i=0;i<=1;i++)
    if (ch[0][i])q.push(ch[0][i]);
    __ temp;
    while (!q.empty())
    {
        temp=q.front();
        q.pop();
        for (int i=0;i<=1;i++)
        {
            if (ch[temp][i])
            p[ch[temp][i]]=ch[p[temp]][i],val[ch[temp][i]]|=val[ch[p[temp]][i]],q.push(ch[temp][i]);//这里就是我说的坑点
            else ch[temp][i]=ch[p[temp]][i];
        }
    }
}
void dfs(__ x)
{
    if (flag)return;
    visited[x]=1;
    ht[x]=1;
    for (int i=0;i<=1;i++)
    {
        if (ch[x][i])
        {
            if (visited[ch[x][i]])
            {
                flag=1;
                return;
            }
            if (!(ht[ch[x][i]]||val[ch[x][i]]))dfs(ch[x][i]);
        }
        if (flag)return;
    }
    visited[x]=0;
}
int main()
{
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        ls=strlen(s);
        __ u=0;
        for (int j=0;j<ls;j++)
        {
            if (!ch[u][s[j]-'0'])ch[u][s[j]-'0']=++len;
            u=ch[u][s[j]-'0'];
        }
        val[u]=1;
    }
    pre();
    dfs(0);
    if (flag)printf("TAK\n");
    else printf("NIE\n");
}