[POI2000] 病毒

洛谷 P2444 传送门

bzoj 2938 传送门

AC自动机的题。

很显然的操作是对所有串建一个AC自动机。

然后我们模拟匹配的过程。

如果能从根开始，一直匹配而不遇到终止节点，那么就找到了一个解。

也就是说，我们的目标是寻找一个根节点能到达的环。

那就在Trie图上DFS就行了。

如果只有in标记，洛谷上能A，lnsyoj上会T三个点。

我们需要额外记录一个v，避免对已经搜过的点再次搜索。

注意，某个点的end要继承他的fail指向的节点的end。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using std::queue;
 5 
 6 int n,sz;
 7 int s[30005][2],ed[30005],fal[30005];
 8 char a[30005];
 9 
10 void insert()
11 {
12     scanf("%s",a+1);
13     int l=strlen(a+1);
14     int p=0;
15     for(int i=1;i<=l;i++)
16     {
17         int c=a[i]-'0';
18         if(!s[p][c])s[p][c]=++sz;
19         p=s[p][c];
20     }
21     ed[p]=1;
22 }
23 
24 void build()
25 {
26     queue<int>qq;
27     for(int i=0;i<=1;i++)qq.push(s[0][i]);
28     while(!qq.empty())
29     {
30         int p=qq.front();
31         qq.pop();
32         for(int i=0;i<=1;i++)
33         {
34             if(s[p][i])
35             {
36                 fal[s[p][i]]=s[fal[p]][i];
37                 ed[s[p][i]]|=ed[fal[s[p][i]]];
38                 qq.push(s[p][i]);
39             }
40             else s[p][i]=s[fal[p]][i];
41         }
42     }
43 }
44 
45 int ans,in[30005],v[30005];
46 
47 void dfs(int p)
48 {
49     if(in[p]){ans=1;return;}
50     if(v[p]||ed[p]||ans)return;
51     in[p]=v[p]=1;
52     for(int i=0;i<=1;i++)dfs(s[p][i]);
53     in[p]=0;
54 }
55 
56 int main()
57 {
58     scanf("%d",&n);
59     for(int i=1;i<=n;i++)insert();
60     build();
61     dfs(0);
62     printf(ans?"TAK":"NIE");
63     return 0;
64 }