AC自动机模板(附详细注释)

ACM/ICPC 字符串 AC自动机模板

#include <iostream>

using namespace std;

struct node
{
int next[26];
int fail;
int count;
void init()
{
memset(next, -1, sizeof(next));
fail = 0;
count = 0;
}
}s[500005];

int sind;
char str[55];
char des[1000005];
int q[500005], qin, qout;

void cas_init()
{
s[0].init();
sind = 1;
}

void ins()
{
int len = strlen(str);
int i, j, ind;
for(i = ind = 0; i < len; i++)
{
j = str[i] - 'a';
if(s[ind].next[j] == -1)
{
s[sind].init();
s[ind].next[j] = sind++;
}
ind = s[ind].next[j];
}
s[ind].count++;
}


void make_fail()
{
qin = qout = 0;
int i, ind, ind_f;
for(i = 0; i < 26; i++)
{
if(s[0].next[i] != -1)
{
q[qin++] = s[0].next[i];
}
}
while(qin != qout)
{
ind = q[qout++];
for(i = 0; i < 26; i++)
{
if(s[ind].next[i] != -1)
{
q[qin++] = s[ind].next[i];
ind_f = s[ind].fail;
while(ind_f > 0 && s[ind_f].next[i] == -1)
ind_f = s[ind_f].fail;
if(s[ind_f].next[i] != -1)
ind_f = s[ind_f].next[i];
s[s[ind].next[i]].fail = ind_f;
}
}
}
}

int fd()
{
int ct = 0;
int di, i, ind, p;
int len = strlen(des);
for(di = ind = 0; di < len; di++)
{
i = des[di] - 'a';
while(ind > 0 && s[ind].next[i] == -1)
ind = s[ind].fail;

if(s[ind].next[i] != -1)
{
ind = s[ind].next[i];

p = ind;
while(p > 0 && s[p].count != -1)
{
ct += s[p].count;
s[p].count = -1;
p = s[p].fail;
}
}
}
return ct;
}

int main()
{
int cas, n;
scanf("%d", &cas);
while(cas-- && scanf("%d", &n))
{
gets(str);

cas_init();
while(n-- && gets(str))
ins();

make_fail();
gets(des);
printf("%d\n", fd());
}
return 0;
}









#include <iostream>

using namespace std;

struct node
{
int next[26];//每一个节点可以扩展到的字母
int fail;//每一个节点的失配指针
int count;//记录每一个可以构成单词的字符串距根节点的深度
void init()//构造
{
memset(next, -1, sizeof(next));//初始化next为-1，即不与任何值相连
fail = 0;//失配指针为空
count = 0;//一开始没有单词赋为0
}
}s[500005];

int sind;//记录
节点的编号
char str[55];//模板串，”单词“
char des[1000005];//”文章“
int q[500005], qin, qout;//队列

void cas_init()//在整个程序前构造root
{
s[0].init();//初始化头结

ACM/ICPC 字符串 AC自动机模板

点
sind = 1;//当前有一个节点
}

void ins()//向书中插入字母
{
int len = strlen(str);//模板串的长度
int i, j, ind;
for(i = ind = 0; i < len; i++)
{
j = str[i] - 'a';//求出字母在next中的编号
if(s[ind].next[j] == -1)//如为空则构造新的，如不为空则顺着上次的开始往下走构造
{
s[sind].init();//初始化当前节点
s[ind].next[j] = sind++;//连向当前节点，并使sind加一来扩充节点
}
ind = s[ind].next[j];//向下遍历
}
s[ind].count++;//增加离根节点这条路径上字符串的个数，一条路上可能不止一个单词
}


void make_fail()//构造失配指针
{
qin = qout = 0;//初始化队列
int i, ind, ind_f;
for(i = 0; i < 26; i++)
{
if(s[0].next[i] != -1)
{
q[qin++] = s[0].next[i];//先考虑根节点，和根节点相连的都入队
}
}
while(qin != qout)
{
ind = q[qout++];//记录队首节点
for(i = 0; i < 26; i++)//遍历队首节点的next
{
if(s[ind].next[i] != -1)//如果节点next不为空
{
q[qin++] = s[ind].next[i];//将儿子节点入队
ind_f = s[ind].fail;//记录节点的失配指针指向
while(ind_f > 0 && s[ind_f].next[i] == -1)//当失配指针不为root时一直循环直到找到一个节点的儿子是i值或到了root
ind_f = s[ind_f].fail;
if(s[ind_f].next[i] != -1)//如果当前节点有儿子的话记录下来备用
ind_f = s[ind_f].next[i];
s[s[ind].next[i]].fail = ind_f;//使当前节点的失配指针指向刚才记录的节点完成失配指针的寻找构造。
}
}
}
}

int fd()
{
int ct = 0;//记录“单词的个数”
int di, i, ind, p;//di为指向“文章”的指针，ind为指向失配节点的指针（即trie树中自匹配的指针）与kmp中next数组中的temp很相似
int len = strlen(des);//“文章的长度”
for(di = ind = 0; di < len; di++)
{
i = des[di] - 'a';
while(ind > 0 && s[ind].next[i] == -1)//当ind指针不是root和找不到节点的儿子是i时一直找下去（即kmp中的while循环）
ind = s[ind].fail;//一直寻找失配指针

if(s[ind].next[i] != -1)//找到了适合的失配指针
{
ind = s[ind].next[i];//指向这个儿子节点，更新ind的值进行下一次匹配

p = ind;//用p来临时代替ind
while(p > 0 && s[p]
.count != -1)//p > 0表示还没到root，count != -1表示指针前还有单词
{
ct += s[p].count;//加上有的单词的个数
s[p].count = -1;//不重复计算，注意这里很重要
p = s[p].fail;//一直寻找失配指

ACM/ICPC 字符串 AC自动机模板

针
}
}
}
return ct;//返回单词个数
}

int main()
{
int cas, n;
scanf("%d", &cas);
while(cas-- && scanf("%d", &n))
{
gets(str);

cas_init();//初始化trie树
while(n-- && gets(str))
ins();//构造trie树

make_fail();//构造失配指针
gets(des);
printf("%d\n", fd());
}
return 0;
}