首页 > 代码库 > AC自动机板子(from. qwer)
AC自动机板子(from. qwer)
#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <iostream>#include <string>#include <queue>using namespace std;const int N=510000;struct Tri{ int Next[N][26], fail[N], val[N], root, L; void init() {L = 0;root = newnode();} int newnode() { for(int i = 0;i < 26;i++) Next[L][i] = -1; val[L++] = 0; return L - 1; } void insert(char s[]) { int len = strlen(s), cur = root; for(int i = 0;i < len;i++) { if(Next[cur][s[i]-‘a‘] == -1) Next[cur][s[i]-‘a‘] = newnode(); cur = Next[cur][s[i]-‘a‘]; } val[cur]++; } void build() { queue<int>Q; fail[root] = root; for(int i = 0;i < 26;i++) if(Next[root][i] == -1) Next[root][i] = root; else { fail[Next[root][i]] = root; Q.push(Next[root][i]); } while(!Q.empty()) { int cur = Q.front(); Q.pop(); for(int i = 0;i < 26;i++) if(Next[cur][i] == -1) Next[cur][i] = Next[fail[cur]][i]; else { fail[Next[cur][i]]=Next[fail[cur]][i]; Q.push(Next[cur][i]); } } } int query(char s[]) { int len = strlen(s), cur = root, res = 0; for(int i = 0;i < len;i++) { cur = Next[cur][s[i]-‘a‘]; int tmp = cur; while (tmp != root) { res += val[tmp]; val[tmp] = 0; tmp = fail[tmp]; } } return res; }};char s[N];Tri AC;int n;int main(){ scanf("%d",&n); AC.init(); for(int i = 0;i < n;i++) { scanf("%s",s); AC.insert(s); } AC.build(); scanf("%s",s); printf("%d\n",AC.query(s)); return 0;}
AC自动机板子(from. qwer)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。