资料
http://www.cnblogs.com/kuangbin/p/3164106.html http://blog.csdn.net/mobius_strip/article/details/22549517
模板 hdu2222
#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#define MAXN 1000000#define LL long longusing namespace std;int read(){ int t=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(f==-1) f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f;}/*-----head-----*/const int SIZ = 26;const int N = 500010;const bool Repeated_match = 0;//是否重复匹配struct Trie{ int cnt,root; int nx[N][SIZ],fail[N],num[N]; queue<int> q; int f(char x){return x-'a';} int newnode() { cnt++; for(int i=0;i<SIZ;i++) nx[cnt][i]=0; num[cnt]=fail[cnt]=0; return cnt; } void init() { cnt=root=0; root=newnode(); } void insert(char *s) { int now=root,len=strlen(s); for(int i=0;i<len;i++) { if(!nx[now][f(s[i])]) nx[now][f(s[i])]=newnode(); now=nx[now][f(s[i])]; } num[now]++; } void build_fail() { fail[root]=root; for(int i=0;i<SIZ;i++) { if(!nx[root][i]) nx[root][i]=root; else fail[nx[root][i]]=root,q.push(nx[root][i]); } while(!q.empty()) { int now=q.front(); for(int i=0;i<SIZ;i++) { if(nx[now][i]) { fail[nx[now][i]]=nx[fail[now]][i]; q.push(nx[now][i]); } else nx[now][i]=nx[fail[now]][i];//构建trie图 } q.pop(); } } int match(char *s) { int sum=0,now=root,temp,len=strlen(s); for(int i=0;i<len;i++) { now=nx[now][f(s[i])]; temp=now; while(temp!=root) { sum+=num[temp]; if(!Repeated_match) num[temp]=0; temp=fail[temp]; } } return sum; }}AC;/*-----AC自动机-----*/int T,n;char a[55],b[1000005];int main(){ T=read(); while(T--) { n=read(); AC.init(); for(int i=1;i<=n;i++) { scanf("%s",a); AC.insert(a); } AC.build_fail(); scanf("%s",b); PRintf("%d/n",AC.match(b)); } return 0;}新闻热点
疑难解答
