Acwing 1053 修复DNA
2022/8/7 23:27:51
本文主要是介绍Acwing 1053 修复DNA,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Acwing 1053 修复DNA
题意:
给出\(n\)个字符串,这些字符串为致病因子,给出一个字符串,求将这些字符串处理成没有致病因子,最少需要改变多少个字符数量
请问,其中有多少个单词在文章中出现了。
思路:
利用AC自动机来实现多字符串匹配,设f[i][j]
为,前i
个字符,当前匹配到j
。
注意标记哪些点不可取,如果当前的前缀不可取,当前点一定也不可取,因为会包含致病因子。
实现:
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int N = 10010, S = 55, M = 100010; int n, tr[N * S][27], cnt[N * S], idx; char str[M]; int q[N * S], ne[N * S]; void insert() { int p = 0; for (int i = 1; str[i]; i++) { int t = str[i] - 'a' + 1; if (!tr[p][t]) tr[p][t] = idx++; p = tr[p][t]; } cnt[p]++; } void build() { int hh = 1, tt = 0; for (int i = 1; i <= 26; i++) if (tr[0][i]) q[++tt] = tr[0][i]; while (hh <= tt) { int t = q[hh++]; for (int i = 1; i <= 26; i++) { int p = tr[t][i]; if (!p) tr[t][i] = tr[ne[t]][i]; else { ne[p] = tr[ne[t]][i]; q[++tt] = p; } } } } int main() { int _; scanf("%d", &_); while (_--) { memset(tr, 0, sizeof tr); memset(cnt, 0, sizeof cnt); memset(ne, 0, sizeof ne); idx = 1; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%s", str + 1); insert(); } build(); scanf("%s", str + 1); int res = 0; for (int i = 1, j = 0; str[i]; i++) { int t = str[i] - 'a' + 1; j = tr[j][t]; int p = j; while (p) { res += cnt[p]; cnt[p] = 0; p = ne[p]; } } printf("%d\n", res); } return 0; }
这篇关于Acwing 1053 修复DNA的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享