[luoguP2444] [POI2000]病毒（AC自动机 + dfs）

传送门

先把所有串建一个AC自动机，

如果要找一个不包含任意一个串的串，

说明这个串一直在AC自动机上匹配但匹配不到，

也就是说，匹配时除去val值为1的点，除去fail指针指向val值为1的点，是否有环，dfs即可。

因为val值为1说明匹配上，fail指针指向的点x，根到x所形成的字符串是当前串的后缀，

所以也得除去fail指针指向val值为1的点的点。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 const int MAXN = 30001; 8 int n, cnt; 9 int ch[MAXN << 2][2], fail[MAXN << 2]; 10 char s[MAXN]; 11 bool vis[MAXN << 2], ins[MAXN << 2], val[MAXN << 2]; 12 queue <int> q; 13 14 inline void insert() 15 23 val[now] = 1; 24 } 25 26 inline void make_fail() 27 40 fail[ch[now][i]] = ch[fail[now]][i]; 41 q.push(ch[now][i]); 42 val[ch[now][i]] |= val[fail[ch[now][i]]]; 43 } 44 } 45 } 46 47 inline bool dfs(int u) 48 59 ins[u] = 0; 60 return 0; 61 } 62 int main() 64 72 make_fail(); 73 if(dfs(0)) puts("TAK"); 74 else puts("NIE"); 75 return 0; 76 }
View Code

上一篇：[POJ1797] Heavy Transportation（最大生成树 || 最短路变形）

下一篇：[codevs3622] 假期（单调队列）

---

dfs AC自动机