\(Description\)

给n个模式串，问是否存在长度无限的主串，使得任何一个模式串都没有在主串中出现。

\(Solution\)

先建AC自动机。

假设我们有了一个无限长的安全代码，然后在AC自动机上匹配应该发生什么？

应该是匹配到一个位置失败跳回去，之后要再匹配到这个位置(必须跳回当前链)再失败跳回去。跳回去就是通过fail指针。

Trie树上连上fail指针的边后（其实就是Build时改的son），如果能在这个有向图上找到环，就TAK。

或者，安全代码无限长的话前后要能拼起来，即前后缀相同(同样要跳回当前链)，且保证在这过程中不会匹配任何模式串。

前后缀相同就是通过fail指针跳回去(到当前链)。

建图（就是建AC自动机），DFS一遍就可以。注意如果fail[x]匹配，那么x也匹配。

注意访问过的点就没必要再访问了。

这题感觉理解不能，感觉AC自动机在从头开始学。。

//1408kb    72ms#include 
    
     #include 
     
      #include 
      
       #include 
       
        const int N=30005;struct AC_Automaton{    int tot,son[N][2],q[N],fail[N];    bool ed[N],vis[N],ins[N];    char s[N];    void Insert()    {        scanf("%s",s);        int l=strlen(s),x=0;        for(int i=0,v; i