【YBTOJ】【Luogu P2444】[POI2000]病毒
2021/6/3 18:22:48
本文主要是介绍【YBTOJ】【Luogu P2444】[POI2000]病毒,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:
洛谷
题目大意:
构造一个无限长的文本串,使得此串不能被匹配。
正文:
好题。我的一开始的思路是,像 01trie 求最大异或那样跑 trie,然后跳失配指针判断合法。但显然假了。
于是得深度思考题意,“不能被匹配”说明跑 trie 时尽量失配,那么在求出失配指针后被修改的 trie 可以往失配方向走。那么只要在 trie 上 DFS 找出一个没有终止标识的环就好了。
代码:
const int N = 3e4 + 10; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } int n; namespace AC { int tot; int t[N][2], g[N][2], fail[N]; bool vis[N], ins[N], f[N]; void Insert(char *s) { int p = 0, len = strlen(s); for (int i = 0; i < len; i++) { int ch = s[i] - '0'; if (!t[p][ch]) g[p][ch] = t[p][ch] = ++tot; p = t[p][ch]; } f[p] = 1; } queue <int> q; void Build() { while (!q.empty()) q.pop(); for (int i = 0; i <= 1; i++) if (t[0][i]) q.push(t[0][i]); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i <= 1; i++) if(t[u][i]) fail[t[u][i]] = t[fail[u]][i], f[t[u][i]] |= f[t[fail[u]][i]], q.push(t[u][i]); else t[u][i] = t[fail[u]][i]; } } bool ans; void DFS(int u) { if (ins[u]) {ans = 1; return;} if(vis[u] || f[u]) return; ins[u] = vis[u] = 1; DFS(t[u][0]), DFS(t[u][1]); ins[u] = 0; } } char s[N]; int main() { n = Read(); for (int i = 1; i <= n; i++) scanf ("%s", s), AC::Insert(s); AC::Build(); AC::DFS(0); puts (AC::ans? "TAK": "NIE"); return 0; }
这篇关于【YBTOJ】【Luogu P2444】[POI2000]病毒的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)