投教网站建设,如何制作游戏,门户wordpress主题,深圳微信建网站正题
题目链接:https://www.luogu.com.cn/problem/P2444 题目大意 nnn个字符串#xff0c;求有没有一个无限的字符串不包含任何一个给出的字符串。 解题思路
考虑ACACAC自动机的匹配方式#xff0c;不过每次我们可以每次在构出的TrieTrieTrie树上随意走#xff08;就是求完…正题
题目链接:https://www.luogu.com.cn/problem/P2444 题目大意
nnn个字符串求有没有一个无限的字符串不包含任何一个给出的字符串。 解题思路
考虑ACACAC自动机的匹配方式不过每次我们可以每次在构出的TrieTrieTrie树上随意走就是求完failfailfail数组之后的TrieTrieTrie树。所以我们如果找到了一个环并且路径上没有任何一个点是其他点的终止位置就好了。
不过对于一个点它的failfailfail树上到根节点的链上有终止节点那么改点的后缀也是一个字符串。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N31000;
int n,cnt,fail[N],ch[N][2];
bool v[N],vis[N],flag;
char s[N];queueint q;
void Make(char *s){int nstrlen(s1),x0;for(int i1;in;i){int cs[i]-0;if(!ch[x][c])ch[x][c]cnt;xch[x][c];}v[x]1;return;
}
void Get_Fail(){for(int i0;i2;i)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){int xq.front();q.pop();for(int i0;i2;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]){flag1;return;}vis[x]1;for(int i0;i2;i)dfs(ch[x][i]);vis[x]0;return;
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%s,s1);Make(s);}Get_Fail();dfs(0); if(flag)printf(TAK);else printf(NIE);return 0;
}
