Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。要搞懂AC自动机，先得有模式树（字典树）Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法，AC自动机是多模式串的字符匹配算法。
要想学好AC自动机，首先你需要了解字典树和KMP
构造字典树
比如说串she，say，her，shr 构造后的图就是：
之所以最后的节点都是灰色的，是标记这个是一个完整的单词的结尾。void insert(char *s) { int len=strlen(s); int root=0; for(int i=0;i<len;i++) { int x=s[i]-'a'; if(!tree[root][x]) { tree[root][x]=pos; pos++; } root=tree[root][x]; } num[root]++;//记录单词的数量 }
构造fail指针
fail的作用：
- 在KMP算法中，当我们比较到一个字符发现失配的时候我们会通过next数组，找到下一个开始匹配的位置，然后进行字符串匹配，当然KMP算法试用与单模式匹配，所谓单模式匹配，就是给出一个模式串，给出一个文本串，然后看模式串在文本串中是否存在。
在AC自动机中，我们也有类似next数组的东西就是fail指针，当发现失配的字符失配的时候，跳转到fail指针指向的位置，然后再次进行匹配操作，AC自动机之所以能实现多模式匹配，就归功于Fail指针的建立。
fail指针的建立：
- 当前节点
有
指针，其
，发现失配，
那么就从这个节点开始再次去进行匹配
。
fail指针的求法：
指针用BFS来求得，对于直接与根节点相连的节点来说，如果这些节点失配，他们的
即可，其他节点其
假设当前节点为，其孩子节点记为
。求
这个节点，然后重复上面过程，如果一直找都找不到，则
eg1eg2
eg3
如图eg3所示
首先的失配指针都指向
接下来该
出队，我们就找
的孩子，则
要出队，我们再找
的
的孩子，故
的
此时队列中有
，
的失配指针
的孩子，则
void getfail() { queue<int>qu; for(int i=0;i<26;i++) { if(tree[0][i])//初始化根节点的26个孩子 { fail[tree[0][i]]=0;//根节点的26个孩子的fail指向根节点0 qu.push(tree[0][i]);//将根节点的孩子压入队列 } } while(!qu.empty( )) { int root=qu.front( );//获得队列里面的一个节点序号root qu.pop( ); for(int i=0;i<26;i++)//遍历这个root节点的26个孩子 { if(tree[root][i])//说明存在root节点的第i个孩子 { fail[tree[root][i]]=tree[fail[root]][i];//root节点的第i个孩子的fail指针指向root->fail的第i个孩子 qu.push(tree[root][i]);//将root的第i个孩子压入队列 } else//root的第i个孩子不存在 { tree[root][i]=tree[fail[root]][i];//那root的第i个孩子节点序号就等于root->fail的第i个孩子的节点序号 } } } }假设当前节点为
然而这个代码只是将(
)的节点序号赋给了
不存在这个
吗?
错了吗？是不是存在疑问呢？答案是没错的。这样是对的。这个就要看
else这个语句了。它的涵义是假如个孩子,于是
while(!qu.empty( )) { int root=qu.front( ); qu.pop( ); for(int i=0;i<26;i++) { if(tree[root][i]) { fail[tree[root][i]]=tree[fail[root]][i]; qu.push(tree[root][i]); } else { tree[root][i]=tree[fail[root]][i]; } } }
文本串的匹配
匹配过程分两种情况：
(1)当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，如果当前匹配的字符是一个单词的结尾，我们可以沿着当前字符的fail指针，一直遍历到根，如果这些节点末尾有标记（此处标记代表，节点是一个单词末尾的标记），这些节点全都是可以匹配上的节点。我们统计完毕后，并将那些节点标记。此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；
(2)当前字符不匹配，则去当前节点失败指针所指向的字符继续匹配，匹配过程随着指针指向root结束。重复这2个过程中的任意一个，直到模式串走到结尾为止。
对照上图，看一下模式匹配这个详细的流程，其中模式串为yasherhs。对于。
中没有对应的路径，故不做任何操作；
时，指针
走到左下节点
信息为1，所以
，并且将节点
循环，这个过程中
时，找不到任何匹配，匹配过程结束。
int query(char *s) { int len=strlen(s); int ans=0; int root=0; for(int i=0;i<len;i++) { int x=s[i]-'a'; root=tree[root][x];//节点序号 for(int j=root;j&&num[j]!=-1;j=fail[j])//j代表的是节点序号 { ans+=num[j]; num[j]=-1; } } return ans; }
Keywords Search
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+100;
int tree[M][26];
int num[M];
int fail[M];
int pos;
void init( )
{
pos=1;
memset(num,0,sizeof(num));
memset(fail,0,sizeof(fail));
memset(tree,0,sizeof(tree));
}
void insert(char *s)
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
tree[root][x]=pos;
pos++;
}
root=tree[root][x];
}
num[root]++;
}
void getfail()
{
queue<int>qu;
for(int i=0;i<26;i++)
{
if(tree[0][i])
{
fail[tree[0][i]]=0;
qu.push(tree[0][i]);
}
}
while(!qu.empty( ))
{
int root=qu.front( );
qu.pop( );
for(int i=0;i<26;i++)
{
if(tree[root][i])
{
fail[tree[root][i]]=tree[fail[root]][i];
qu.push(tree[root][i]);
}
else
{
tree[root][i]=tree[fail[root]][i];
}
}
}
}
int query(char *s)
{
int len=strlen(s);
int ans=0;
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
root=tree[root][x];
for(int j=root;j&&num[j]!=-1;j=fail[j])
{
ans+=num[j];
num[j]=-1;
}
}
return ans;
}
int main( )
{
int t,n;
char s[1000010];
scanf("%d",&t);
while(t--)
{
init( );
scanf("%d",&n);
getchar( );
while(n--)
{
scanf("%s",s);
insert(s);
}
fail[0]=0;
getfail( );
scanf("%s",s);
printf("%d\n",query(s));
}
return 0;
}
链接三连：
