做网站引流到天猫,wordpress后台进去,久久诗词网,w3c标准网站http://acm.hdu.edu.cn/showproblem.php?pid2222 一个AC自动机的模板题。用的kuangbin的模板#xff0c;静态建Trie树。可能遇到MLE的情况要转动态建树。 AC自动机的讲解看这里 http://blog.csdn.net/niushuai666/article/details/7002823 http://blog.csdn.net/mobius_strip…http://acm.hdu.edu.cn/showproblem.php?pid2222 一个AC自动机的模板题。用的kuangbin的模板静态建Trie树。可能遇到MLE的情况要转动态建树。 AC自动机的讲解看这里 http://blog.csdn.net/niushuai666/article/details/7002823 http://blog.csdn.net/mobius_strip/article/details/22549517 /*--------------------------------------------------------------------------------------*/
// Helicas header
// Second Editions
// 2015.11.7
//
#include algorithm
#include iostream
#include cstring
#include ctype.h
#include cstdlib
#include cstdio
#include vector
#include string
#include queue
#include stack
#include cmath
#include set
#include map//debug function for a N*M array
#define debug_map(N,M,G) printf(\n);for(int i0;i(N);i)\
{for(int j0;j(M);j){\
printf(%d,G[i][j]);}printf(\n);}
//debug function for int,float,double,etc.
#define debug_var(X) cout#XXendl;
/*--------------------------------------------------------------------------------------*/
using namespace std;int N,M,T;struct Trie
{int next[500010][26],fail[500010],end[500010];int root,L;int newnode(){for(int i0;i26;i) next[L][i] -1;end[L] 0;return L-1;}void init(){L 0;root newnode();}void insert(char *s){int len strlen(s);int now root;for(int i0;ilen;i){if(next[now][s[i]-a] -1)next[now][s[i]-a] newnode();now next[now][s[i]-a];}end[now];}void build(){queue int Q;fail[root] root;for(int i0;i26;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 now Q.front();Q.pop();for(int i0;i26;i){if(next[now][i] -1)next[now][i] next[fail[now]][i];else{fail[next[now][i]] next[fail[now]][i];Q.push(next[now][i]);}}}}int query(char *s){int len strlen(s);int now root;int ans 0;for(int i0;ilen;i){now next[now][s[i]-a];int temp now;while(temp ! root){ans end[temp];end[temp] 0;temp fail[temp];}}return ans;}void debug(){for(int i0;iL;i){printf(id %3d,fail %3d,end %3d,chi [,i,fail[i],end[i]);for(int j0;j26;j)printf(%2d,next[i][j]);printf(]\n);}}
};char buf[1000100];
Trie ac;int main()
{scanf(%d,T);while(T--){ac.init();scanf(%d,N);for(int i0;iN;i){scanf(%s,buf);ac.insert(buf);}ac.build();//ac.debug();scanf(%s,buf);printf(%d\n,ac.query(buf));}
} 第N次入门AC自动机。。。成功。。。转载于:https://www.cnblogs.com/helica/p/5037814.html
