Keywords Search hdu2222 ac自动机

2019-11-06 07:25:22

字体：大中小

来源：转载

供稿：网友

Description

给定T组数据n个单词一个字符串s求s中有多少给出的单词出现

Solution

~~无力吐槽题号~~

ac自动机裸题模板，学习了所谓ac自动机就是一棵带fail指针的trie，t(i)的fail表示作为t(i)后缀的另一字符串的前缀位置，然后这个fail是可以bfs出来的

还有就是最好记路strlen不然每次会TLE。神奇

辣鸡csdn卡死害我重写了三遍

Code

#include <stdio.h>#include <string.h>#include <queue>#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define fill(x, t) memset(x, t, sizeof(x))#define N 500005#define L 27using namespace std;int rc[N][L], p[N], f[N], cnt, len;char s[1000001];inline void getFail(){ queue<int> q; rep(i, 'a', 'z'){ if (rc[0][i - 'a']){ q.push(rc[0][i - 'a']); } } while (!q.empty()){ int now = q.front(); q.pop(); rep(i, 'a', 'z'){ if (rc[now][i - 'a']){ q.push(rc[now][i - 'a']); int v = f[now]; while (v && !rc[v][i - 'a']){ v = f[v]; } f[rc[now][i - 'a']] = rc[v][i - 'a']; } } }}inline void insert(){ int now = 0; rep(i, 0, len - 1){ int tar = s[i] - 'a'; if (!rc[now][tar]){ rc[now][tar] = ++ cnt; } now = rc[now][tar]; } p[now] += 1;}inline void query(){ int now = 0; int ans = 0; rep(i, 0, len - 1){ int tar = s[i] - 'a'; while (now && !rc[now][tar]){ now = f[now]; } now = rc[now][tar]; for (int tmp = now; tmp; tmp = f[tmp]){ ans += p[tmp]; p[tmp] = 0; } } PRintf("%d/n", ans);}int main(void){ int T; scanf("%d", &T); while (T --){ cnt = 0; fill(rc, 0); fill(f, 0); fill(p, 0); int n; scanf("%d", &n); rep(i, 1, n){ scanf("%s", s); len = strlen(s); insert(); } getFail(); scanf("%s", s); len = strlen(s); query(); } return 0;}

上一篇：lucene--索引的创建

下一篇：《剑指Offer》面试题四之替换空格

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注