推荐博客：http://www.cnblogs.com/kuangbin/p/3164106.html AC自动机小结
https://blog.csdn.net/creatorx/article/details/71100840 AC自动机最详细的解释
2006年国家集训队论文：Trie图的构建、活用与改进 王赟
1.(HDOJ2222)http://acm.hdu.edu.cn/showproblem.php?pid=2222
题意：求目标串中出现了几个模式串。
分析：AC自动机模板题
1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn=500010; 8 9 struct Trie 10 { 11 int nxt[maxn][26],fail[maxn],end[maxn]; //nxt为字典树, fail相当于kmp中的nxt数组, end对单词结尾做标记 12 int root,L; //L相当于字典树中的sz ，root为根节点（即；0） 13 int newnode() //初相当于始化一个字典树上的节点 14 { 15 for ( int i=0;i<26;i++ ) nxt[L][i]=-1; 16 end[L++]=0; 17 return L-1; 18 } 19 void init() 20 { 21 L=0; 22 root=newnode(); 23 } 24 void insert(char buf[]) //大致于字典树插入过程相同 25 { 26 int len=strlen(buf); 27 int now=root; 28 for ( int i=0;i
que; 39 fail[root]=root; //根节点初始化为0(即其本身) 40 for (int i=0;i<26;i++ ) 41 { 42 if ( nxt[root][i]==-1 ) nxt[root][i]=root; 43 else //Trie中已经构建的节点 44 { 45 int x=nxt[root][i]; 46 fail[x]=root; 47 que.push(x); 48 } 49 } 50 while ( !que.empty() ) 51 { 52 int now=que.front(); 53 que.pop(); 54 for ( int i=0;i<26;i++ ) 55 { 56 if ( nxt[now][i]==-1 ) //无后继点 57 nxt[now][i]=nxt[fail[now]][i];//类似于kmp中求nxt数组一样 58 else //存在下一个节点 59 { 60 int x=nxt[now][i]; 61 fail[x]=nxt[fail[now]][i];//失配指针指向他父节点的失配指针的下一个相同字符处 62 que.push(x); 63 } 64 } 65 } 66 } 67 int query(char buf[]) //相当于字典树中的访问操作 68 { 69 int len=strlen(buf); 70 int now=root; 71 int res=0; 72 for ( int i=0;i
AC自动机模板（含解释） 1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int maxn=500010; 8 const int maxm=26; 9 10 struct Trie 11 { 12 int nxt[maxn][maxm],fail[maxn],end[maxn]; 13 int root,L; 14 int newnode() 15 { 16 for ( int i=0;i
que; 41 fail[root]=root; 42 for (int i=0;i
这样的矩阵。