首页 > 代码库 > HDU 2222
HDU 2222
第一题AC自动机,高仿代码!
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int maxn = 500010;char str[1000010];struct ACAutomaton{ int ch[maxn][26],fail[maxn],val[maxn],last[maxn],sz,root; int newnode(){ memset(ch[sz],0,sizeof(ch[sz])); val[sz] = 0; return sz++; } void init(){ sz = 0; root = newnode(); } void insert(char *str){ int len = strlen(str); int now = root; for(int i = 0;i < len;i++){ int &tmp = ch[now][str[i]-‘a‘]; if(!tmp) tmp = newnode(); now = tmp; } val[now]++; } void getfail(){ queue<int> q; fail[root] = root; for(int i = 0;i < 26;i++){ int u = ch[root][i]; if(u){ fail[u] = last[u] = 0; q.push(u); } } while(!q.empty()){ int now = q.front();q.pop(); for(int i = 0;i < 26;i++){ int u = ch[now][i]; if(!u) ch[now][i] = ch[fail[now]][i]; else{ fail[u] = ch[fail[now]][i]; last[u] = val[fail[u]] ? fail[u]:last[fail[u]]; q.push(u); } } } } int query(char *str){ int len = strlen(str); int now = root; int ret = 0; for(int i = 0;i < len;i++){ now = ch[now][str[i]-‘a‘]; int tmp = now; while(tmp != root && val[tmp]){ ret += val[tmp]; val[tmp] = 0; tmp = last[tmp]; } } return ret; }}ac;int main(){ int kase,n; scanf("%d",&kase); while(kase--){ ac.init(); scanf("%d",&n); for(int i = 0;i < n;i++){ scanf("%s",str); ac.insert(str); } ac.getfail(); scanf("%s",str); printf("%d\n",ac.query(str)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。