Acwing 1282 搜索关键词
2022/8/7 23:26:24
本文主要是介绍Acwing 1282 搜索关键词,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Acwing 1282 搜索关键词
题意:
给定 \(n\) 个长度不超过 \(50\)的由小写英文字母组成的单词,以及一篇长为\(m\)的文章。
请问,其中有多少个单词在文章中出现了。
思路:
AC自动机模板题目
但是由于匹配到的是和当前的的字符串最长的字符位置,但是可能里面包含则其他单词,所以要不断的找和当前最长的公共前后缀。
实现:
#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 1282 搜索关键词的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-03-28Elasticsearch - kibana画图
- 2024-03-28我最近买的书里面带的CD盘,放电脑里后,说是0字节,但是可以播放,不能把里面的东西复制出来
- 2024-03-26sqlalchemy.exc.objectnotexecutableerror: not an executable object
- 2024-03-26no dashboards are active for the current data set
- 2024-03-26torch sum
- 2024-03-26format' is not a recognized built-in function name
- 2024-03-26sources list kali
- 2024-03-26matlab p code
- 2024-03-26mean of empty slice
- 2024-03-26unable to attach or mount volumes: unmounted volumes