luogu2444(POI)

发表于 | 分类于

这是一道对于AC自动机很好的一个应用。

正常情况下，我们都是希望字符串尽可能的去匹配，这道题则是在匹配完成之前尽可能地转移。于是按照AC自动机的思路我们先建出trie树并构造出fail指针，然后从根开始深搜，如果搜到一个环则我们可以在这个环上不断地构建安全代码，否则无解。在深搜时要注意，我们只能向安全节点（无结束标记的节点）转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct trie{
    int nxt[2];
    int fail;
    int nd;
};
int tot;
trie ac[30400];
int n;
char ch[2003];
inline void add(char *c)
{
    int len=strlen(c);
    int k=0;
    for(int i=0;i<len;i++)
    {
        int j=c[i]-'0';
        if(ac[k].nxt[j]==0)
            ac[k].nxt[j]=++tot;
        k=ac[k].nxt[j];
    }
    ac[k].nd++;
}
inline void find_fail()
{
    queue<int>q;
    int r=0;
    for(int i=0;i<2;i++)
    {
        if(ac[r].nxt[i])q.push(ac[r].nxt[i]);
        ac[ac[r].nxt[i]].fail=0;
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<2;i++)
        {
            if(ac[t].nxt[i])
            {
                ac[ac[t].nxt[i]].fail=ac[ac[t].fail].nxt[i];
                q.push(ac[t].nxt[i]);
            }
            else ac[t].nxt[i]=ac[ac[t].fail].nxt[i];
            if(ac[ac[t].fail].nd)ac[t].nd=1;
        }
    }
}
int vis[32500];
int acn[32099];
void dfs(int d)
{  
    vis[d]=1;
    for(int i=0;i<=1;i++) 
        if(vis[ac[d].nxt[i]])
        { 
            printf("TAK");
            exit(0); 
        }
        else if(ac[ac[d].nxt[i]].nd==0&&acn[ac[d].nxt[i]]==0)
        {
            acn[ac[d].nxt[i]]=1;
            dfs(ac[d].nxt[i]);
        }
    vis[d]=0; 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch);
        add(ch);
    }
    find_fail();
    dfs(0);
    printf("NIE");
    return 0;
}