[日常摸魚][POI2000]病毒-Tire圖（AC自動機）+dfs

https://www.luogu.org/problemnew/show/P2444

（沒有bzoj權限号T_T）

字元串題對我這種傻逼來說真是太難了x

題意：輸入$n$個01組成的模式串串，判斷是否存在一個無限長的01串滿足任何給定的模式串都不是這個串的子串，$n \leq 2000,\sum len(str) \leq 30000$

首先用模式串構造出AC自動機（其實應該叫Trie圖），題目要求的串如果存在，那就相當于在Trie圖上存在一個環，這個環不包含任何一個模式串，是以隻要構造出來Tire圖判斷是否存在這樣子的環，注意如果Tire圖上的某個點$x$是一個模式串的結尾，那麼不僅不能夠經過$x$，而且不能經過所有包含這個字尾的串，根據$fail$指針的定義就可以直接這樣寫：

danger[tr[k][i]]|=danger[fail[tr[k][i]]];      

完整的代碼：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=30005;
int n,cnt;
int tr[N][2],fail[N];
bool danger[N],vis[N],mark[N],flag;
char s[N];
queue<int>q;
inline void insert(char *c)
{
    int len=strlen(c+1),k=0;
    for(register int i=1;i<=len;i++)
    {
        int t=c[i]-'0';
        if(!tr[k][t])tr[k][t]=++cnt;
        k=tr[k][t];
    }danger[k]=1;
}

inline void build()
{
    if(tr[0][0])fail[tr[0][0]]=0,q.push(tr[0][0]);
    if(tr[0][1])fail[tr[0][1]]=0,q.push(tr[0][1]);
    while(!q.empty())
    {
        int k=q.front();q.pop();
        for(register int i=0;i<=1;i++)
        {
            if(!tr[k][i])tr[k][i]=tr[fail[k]][i];
            else
            {
                fail[tr[k][i]]=tr[fail[k]][i];
                danger[tr[k][i]]|=danger[fail[tr[k][i]]];//
                q.push(tr[k][i]);
            }
        }
    }
}

inline int dfs(int x)
{
    vis[x]=1;
    for(register int i=0;i<=1;i++)
    {
        int k=tr[x][i];
        if(vis[k])return 1;
        if(mark[k]||danger[k])continue;
        mark[k]=1;
        if(dfs(k))return 1;
    }
    vis[x]=0;return 0;
}

int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
    {
        scanf("%s",s+1);insert(s);
    }
    build();
    if(dfs(0))printf("TAK");
    else printf("NIE");
    return 0;
}      

View Code

轉載于:https://www.cnblogs.com/yoooshinow/p/8168105.html