AC自动机---个人总结
2024-08-28 19:18:06
比较好的 AC自动机算法详解..
【转】http://www.cppblog.com/mythit/archive/2009/04/21/80633.html
个人总结:【图是盗用的..】
ac自动机是用来求出:给出n个单词,和一篇文章arr[],问arr中出现了多少个单词..
第一步:根据给出的n个单词构造一棵字典树
第二步:根据字典树完成失配指针
第三步:枚举文章中的每个字符,并根据拥有了失配指针的字典树 查找 出现的单词个数
以单词:say she shr he her 文章:yasherhs 举例:
第一步:根据给出的n个单词构造一棵字典树
const int kind = ;
struct node{
node *fail; //失败指针
node *next[kind]; //Tire每个节点的个子节点(最多个字母)
int count; //是否为该单词的最后一个节点
node(){ //构造函数初始化
fail=NULL;
count=;
memset(next,NULL,sizeof(next));
}
}*q[]; //队列,方便用于bfs构造失败指针
char keyword[]; //输入的单词
char str[]; //模式串
int head,tail; //队列的头尾指针
结构体
void insert(char *str,node *root){
node *p=root;
int i=,index;
while(str[i]){
index=str[i]-'a';
if(p->next[index]==NULL) p->next[index]=new node();
p=p->next[index];
i++;
}
p->count++; //在单词的最后一个节点count+1,代表一个单词
}
构造字典树
第二步:根据字典树完成失配指针
<结果是 (she)每一个字符(s,h,e)都会指向自己上一个字符(root,s,h)的失配指针(root,root,root->h)后的和当前字符匹配((如果没有则指向root)root, root->h, root->h->e)的字符>
即结果是保证树中的节点(node)会指向拥有相同字符串(parents->..->node = root->..->node',parents表示某个祖先节点,node'表示相同字符节点)的枝桠(没有则指向root)
void build_ac_automation(node *root){
int i;
root->fail=NULL;
q[head++]=root;
while(head!=tail){
node *temp=q[tail++];
node *p=NULL;
for(i=;i<;i++){
if(temp->next[i]!=NULL){
if(temp==root) temp->next[i]->fail=root;
else{
p=temp->fail;
while(p!=NULL){
if(p->next[i]!=NULL){
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
完成失配指针
第三步:枚举文章中的每个字符,并根据拥有了失配指针的字典树 查找 出现的单词个数 <cnt += node.cnt>
int query(node *root){
int i=,cnt=,index,len=strlen(str);
node *p=root;
while(str[i]){
index=str[i]-'a';
while(p->next[index]==NULL && p!=root) p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root && temp->count!=-){
cnt+=temp->count;
temp->count=-;
temp=temp->fail;
}
i++;
}
return cnt;
}
查找
查找方法是如果上一个字符的下一个字符和当前字符匹配,则加上node.cnt,并不断按照失配指针查找出现的单词,不断加上node.cnt
失配,则根据失配指针去找可能匹配的出现的单词,找到则加上node.cnt
最新文章
- [LeetCode] Fizz Buzz 嘶嘶嗡嗡
- c语言经典算法——猴子偷桃问题
- 用python监控Linux,CPU,内存,硬盘
- HDU 2588 GCD (欧拉函数)
- [LeetCode][Python]ZigZag Conversion
- android studio 快捷笔记
- JavaScript的原型继承
- JavaScript 闭包环境非常奇特 - 相当于类与实例的关系?!
- redis和redis php扩展安装(转)
- Chrome浏览器网页截全屏算法以及实现
- SharePoint 2016 修改左上角连接
- Hibernate学习笔记(五) — 多对多关系映射
- OO第一次blog
- QT 13 窗口屏幕设置大小与居中显示
- Hacked VisualSVN Server by PHP to allow user change password
- ubuntu 禁用 guest 账户
- centos6与centos7区别
- 【IT笔试面试题整理】有序数组生成最小高度二叉树
- Oracle RMAN 恢复数据库到不同主机(二)
- Android 5.0 API