正題

題目鏈接:https://www.luogu.com.cn/problem/P2444

---

題目大意

$n$個字符串，求有沒有一個無限的字符串不包含任何一個給出的字符串。

---

解題思路

考慮$AC$自動機的匹配方式，不過每次我們可以每次在構(gòu)出的$Trie$樹上隨意走（就是求完$fail$數(shù)組之后的$Trie$樹）。所以我們?nèi)绻业搅艘粋€環(huán)并且路徑上沒有任何一個點是其他點的終止位置就好了。

不過對于一個點，它的$fail$樹上到根節(jié)點的鏈上有終止節(jié)點，那么改點的后綴也是一個字符串。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=31000; int n,cnt,fail[N],ch[N][2]; bool v[N],vis[N],flag; char s[N];queue<int> q; void Make(char *s){int n=strlen(s+1),x=0;for(int i=1;i<=n;i++){int c=s[i]-'0';if(!ch[x][c])ch[x][c]=++cnt;x=ch[x][c];}v[x]=1;return; } void Get_Fail(){for(int i=0;i<2;i++)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<2;i++)if(!ch[x][i])ch[x][i]=ch[fail[x]][i];else{fail[ch[x][i]]=ch[fail[x]][i];v[ch[x][i]]|=v[fail[ch[x][i]]];q.push(ch[x][i]);}}return; } void dfs(int x){if(flag||v[x])return;if(vis[x]){flag=1;return;}vis[x]=1;for(int i=0;i<2;i++)dfs(ch[x][i]);vis[x]=0;return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);Make(s);}Get_Fail();dfs(0); if(flag)printf("TAK");else printf("NIE");return 0; }

總結(jié)

以上是生活随笔為你收集整理的P2444-[POI2000]病毒【AC自动机】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。