【模板】AC自动机

模板1

#include <queue> #include <cstdio> #include <cstring> #define N 1000001 int n, cnt, ans; int next[N][26], val[N], fail[N]; char s[N]; std::queue <int> q; inline void insert() val[now]++; } inline void make_fail() fail[next[now][i]] = next[fail[now]][i]; q.push(next[now][i]); } } } inline void ac() } } int main() make_fail(); scanf("%s", s + 1); ac(); printf("%d\n", ans); return 0; }

　　

模板2

#include <queue> #include <cstdio> #include <cstring> #define N 1000001 #define max(x, y) ((x) > (y) ? (x) : (y)) int n, cnt; int val[N], next[N][26], ans[N], fail[N]; char s1[151][71], s2[N]; std::queue <int> q; inline void insert(int k, char *s) val[now] = k; } inline void make_fail() fail[next[now][i]] = next[fail[now]][i]; q.push(next[now][i]); } } } inline void ac(char *s) for(i = 1; i <= n; i++) ans[0] = max(ans[0], ans[i]); printf("%d\n", ans[0]); for(i = 1; i <= n; i++) if(ans[i] == ans[0]) printf("%s\n", s1[i] + 1); } int main() make_fail(); scanf("%s", s2 + 1); ac(s2); } return 0; }

　　

上一篇：[BZOJ1579] [Usaco2009 Feb]Revamping Trails 道路升级（分层图最短路 + 堆优化dijk）

下一篇：[BZOJ1604] [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居（好题）

---

模板 AC自动机