题面

　　

解析

　　讲AC自动机时的例题， 还是很有意思，我改了无数遍终于改出来了。在某谷上AC后， 被bzoj击杀了，先是TLE， 然后又是WA， 终于AC了， 不容易啊。

　　思路还是比较简单，既然存在无限长的路径， 那就一定存在一个循环节， 在补全的AC自动机上，一个环就是一个循环节， 如果这个环不经过任何一个终止节点，那就存在一个合法循环节

　　在建立补全的AC自动机时，每一个节点要与它的fail节点取或， 也就是继承它fail节点的标记， 因为它fail节点的根缀就是这个节点的后缀，如果fail节点不可取， 那这个节点也不可取。建完补全的AC自动机后，在原图上跑dfs， 因为是有向边， 所以进入节点时要打上标记，而退出节点时要撤销标记， 但为了不重复地遍历每一个节点，需要另外在进入节点时打上访问标记，防止其它点再次进入这个点遍历（就是防止TLE）

　　还有一些我在做这个题时的疑惑。一是自环合不合法， 其实是合法的， 因为某个点走了某一条边后再次回到这个节点，说明这个循环节长度只有一，循环节就是走的这条边。还有就是根节点也是可走的，回到根节点其实也是一个循环节，只是这个无限长的字符串的循环节前不存在其它字符罢了

　　代码：

#include
      
       using namespace std;const int maxn = 100005;int n, tot, go[maxn][2], fail[maxn];char s[maxn];bool ed[maxn];void Add(){    int now = 0;    int len = strlen(s);    for(int i = 0; i < len; ++i)    {        if(!go[now][s[i]-'0'])            go[now][s[i]-'0'] = ++tot;        now = go[now][s[i]-'0'];    }    ed[now] = 1;}queue
       
         q;void getfail(){    for(int i = 0; i <= 1; ++i)        if(go[0][i])            q.push(go[0][i]);    while(!q.empty())    {        int st = q.front();        q.pop();        for(int i = 0; i <= 1; ++i)            if(go[st][i])            {                q.push(go[st][i]);                int t = fail[st];                while(t && !go[t][i])    t = fail[t];                fail[go[st][i]] = go[t][i];                        ed[go[st][i]] |= ed[fail[go[st][i]]];            }            else                go[st][i] = go[fail[st]][i];    }}bool vis[maxn], used[maxn];void dfs(int x){    vis[x] = used[x] = 1;    for(int i = 0; i < 2; ++i)    {        int id = go[x][i];        if(ed[id])    continue;        if(vis[id])        {            printf("TAK");            exit(0);        }        if(!used[id])            dfs(id);    }    vis[x] = 0;}int main(){    scanf("%d", &n);    for(int i = 1; i <= n; ++i)    {        scanf("%s", s);        Add();    }    getfail();    dfs(0);    printf("NIE");    return 0;}