P2444 [POI2000] 病毒

2018-05-17 19:21:20


AC自动机

询问是否存在无限长的不含目标串的字符串

试想一下,如果把这个无限长的字符串插入到AC自动机中,会发生什么?

没错,我们永远不会跳到目标串结尾的位置(在自动机里转圈圈~~)

所以最终任务变成:在fail树上寻找一个环,使其上不包含危险节点(即不包含目标串结尾的节点),并且从根节点0可以到达这个环

因此在getfail指针的过程中,需要把危险节点的标记传递到它的子节点

然后就可以从根节点开始dfs,一旦找到环,就说明存在无限长的字符串,直接退出

注意这里要开两个数组,一个是访问标记,用来找环

一个是历史访问的记录,在dfs的时候不递归历史访问过且不在搜索栈中的节点

%一%夫哥 @beretty

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int N=3e4+5;
int n;
char s[N];
struct Aho_Corasick_automation
{
    int ch[N][2],val[N],fail[N],cnt;
    bool vis[N],f[N];
    inline void insert(char *s)
    {
        int len=strlen(s+1),u=0;
        for (int i=1;i<=len;i++)
        {
            int v=s[i]-'0';
            if (!ch[u][v]) ch[u][v]=++cnt;
            u=ch[u][v];
        }
        ++val[u];
    }
    inline void getfail()
    {
        queue<int>q;
        for (int i=0;i<2;i++)
        {
            int v=ch[0][i];
            if (v) q.push(v);
        }
        while (!q.empty())
        {
            int u=q.front(); q.pop();
            for (int i=0;i<2;i++)
            {
                int v=ch[u][i];
                if (v)
                {
                    q.push(v);
                    fail[v]=ch[fail[u]][i];
                    val[v]|=val[ch[fail[u]][i]];
                }
                else ch[u][i]=ch[fail[u]][i];
            }
        }
    }
    void dfs(int k)
    {
        vis[k]=1;
        for (int i=0;i<2;i++)
        {
            int v=ch[k][i];
            if (vis[v])
            {
                puts("TAK"); exit(0);
            }
            if (!val[v]&&!f[v])
            {
                f[v]=1; dfs(v);
            }
        }
        vis[k]=0;
    }
}AC;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        AC.insert(s);
    }
    AC.getfail(); AC.dfs(0); puts("NIE");
    return 0;
}