Keywords Search hdu2222 ac自动机

Description

---

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

Solution

---

无力吐槽题号

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

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

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

为了应对MLE这里补上指针版本的

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 27 using 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; } #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 1001001 struct node{ node *next[26]; node *fail; int count; node(){ fail = NULL; rep(i, 0, 25){ next[i] = NULL; } count = 0; } }*root; inline void ins(char *str){ node *now = root; int len = strlen(str); rep(i, 0, len - 1){ int tar = str[i] - 'a'; if (now->next[tar] == NULL){ now->next[tar] = new node(); } now = now->next[tar]; } now->count += 1; } using std:: queue; queue<struct node *> que; inline void getFail(){ int head = 0, tail = 0; que.push(root); while (!que.empty()){ node *now = que.front(); que.pop(); rep(i, 0, 25){ if (now->next[i] != NULL){ if (now == root){ now->next[i]->fail = root; }else{ node *tmp = now->fail; while (tmp != NULL){ if (tmp->next[i] != NULL){ now->next[i]->fail = tmp->next[i]; break; } tmp = tmp->fail; } if (tmp == NULL){ now->next[i]->fail = root; } } que.push(now->next[i]); } } } } inline int query(char *str){ int len = strlen(str); int ret = 0; node *now = root; rep(i, 0, len - 1){ int tar = str[i] - 'a'; while (now->next[tar] == NULL && now != root){ now = now->fail; } now = now->next[tar]; if (now == NULL){ now = root; } node *tmp = now; while (tmp != root && tmp->count != -1){ ret += tmp->count; tmp->count = -1; tmp = tmp->fail; } } return ret; } char str[N]; int main(void){ int T; scanf("%d", &T); while (T --){ int n; scanf("%d", &n); root = new node(); rep(i, 1, n){ scanf("%s", str); ins(str); } scanf("%s", str); getFail(); int ans = query(str); printf("%d\n", ans); } return 0; }