AC自动机-字符串多模匹配神器
目录
1.hdoj 2222 keywords search(简单模版题)
2.hihocoder hiho218 Keywords Filter
一.什么是AC自动机?
首先,这并不是会自动帮你ac题目的机器,ac自动机全名Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。
在打开这篇博客还不知道字典树以及KMP算法的人可以先去我另外两篇博客了解一下字典树以及KMP:
之所以需要先了解这两个知识是因为AC自动机用到了这两个算法的核心思维.下面的讲解不对这两个知识多加讲解.
二.AC自动机用来干嘛?
用来做字符串多模匹配,什么叫多模匹配呢,最标志性的问题就是现在有n个单词和一段长为m的文章,我要你回答这段文章中这n个单词的出现情况,这种问题就是AC自动机最拿手的问题.
三.AC自动机实现思路
首先我们对于这个经典问题:有n个单词和一段长为m的文章,我要你回答这段文章中这n个单词的出现情况.
第一步:建立字典树
我们会先建立一个包含这n个单词的字典树以此完成对n个单词的存储.
struct node{
node *fail; //失败指针,此节点失配时将跳向fail所指节点
int end; //此值表示以此节点为结尾的单词个数
node *next[26]; //指向子节点
}root;字典树的结点如上,字典树构造就不说了,看我那篇博客 字典树详解 ,多的这个fail指针第二步会细说.
第二步:构造字典树的fail指针
然后我们需要了解一个叫失败指针的东西,失败指针的概念和KMP中的next数组很类似,失败指针会被附加到每一个字典树结点上,意义是当匹配在此节点失配时,跳转向失败指针所指结点继续匹配,这个结点其实就是与之前的模式串具有最长公共前后缀的结点,直到跳到根结点还是没有匹配上的话继续匹配文章中下一个字符,fail指针对于所有模式串之间最长公共前后缀的利用是使文章与字典树中所有模式串高速匹配的核心.
这里举一个简例:有单词abc bce cd,现在的文章是abcd
构造出的字典树没有画fail时的样子:
构造出的字典树有fail时的样子:
(注:结点内数字的意义是end,边上的字母指的是next指针所代表字母,红色线条为失败指针)
abc中c的fail指针为什么指向bce的c呢?因为abc和bce的最长相同前后缀为bc,长度为2,abc与cd最长相同前后缀为c,长度为1,选最长的.
代码中可以发现除了围起来的核心代码,其余部分就是一个对字典树的bfs,而核心部分也很好理解
1.对于根结点下属结点,其fail指针直接指向根结点
2.对于其它结点不断向上找父节点的fail,直到出现p->next[i]存在的结点,或者一直找到根节点还没找到(只有根节点的fail为NULL),则将之fail指针指向根节点
void build_fail(){ //构造ac自动机的失败指针
queue<node *> q;
q.push(&root);
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++){
if(t->next[i]){
if(t==&root) t->next[i]->fail=&root;
else{
node *p=t->fail;
while(p!=NULL){
if(p->next[i]){
t->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) t->next[i]->fail=&root;
}
q.push(t->next[i]);
}
}
}
}第三步:执行文章与字典树与模式匹配
从树的根节点和文章第一个字符开始,成功时记录,失败时跟着fail指针跳,跳到根为止开始文章下一个字符.
四.模版代码
思路走到上面已经差不多了,至于怎么用代码实现出来?每个人的实现方法不同,满足上面这些思维与目的的代码都可以说是ac自动机,下面放上我自己写的模版代码仅作参考.
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <malloc.h>
using namespace std;
const int maxkeywordlen=51;
const int maxstrlen=1000001;
char keyword[maxkeywordlen],str[maxstrlen];
int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x]
void init_charmapping(){
for(int i='a';i<='z';i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便.
charmapping[i]=i-'a';
}
}
struct node{
node *fail; //失败指针,此节点失配时将跳向fail所指节点
int end; //此值表示以此节点为结尾的单词个数
node *next[26]; //指向子节点
}root;
node *getnode(){ //构造 一个新结点并做好初始化,返回指向该节点的指针
node *newnode=(node *)malloc(sizeof(node));
newnode->end=0;
newnode->fail=NULL;
for(int i=0;i<26;i++) newnode->next[i]=NULL;
return newnode;
}
void insert(char *s){ //向ac自动机加入字符串s
int k=0,temp;
node* t=&root;
for(int i=0;s[i];i++){
temp=charmapping[s[i]];
if(!t->next[temp]) t->next[temp]=getnode();
t=t->next[temp];
}
t->end++;
}
void build_fail(){ //构造ac自动机的失败指针
queue<node *> q;
q.push(&root);
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++){
if(t->next[i]){
if(t==&root) t->next[i]->fail=&root;
else{
node *p=t->fail;
while(p!=NULL){
if(p->next[i]){
t->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) t->next[i]->fail=&root;
}
q.push(t->next[i]);
}
}
}
}
void free_trie(){ //释放ac自动机, 只留根节点
queue<node *> q;
for(int i=0;i<26;i++){
if(root.next[i]){
q.push(root.next[i]);
root.next[i]=NULL;
}
}
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++) if(t->next[i]) q.push(t->next[i]);
free(t);
}
}
int match(char *s){ //计算ac自动机中所有模式串在字符串s中出现的次数之和,不同题目match不同写法
node *now=&root;
int ans=0;
for(int i=0;s[i];i++){
int temp=charmapping[s[i]];
if(now->next[temp]) now=now->next[temp];
else{
node* p=now->fail;
while(p!=NULL&&p->next[temp]==NULL) p=p->fail;
if(p==NULL) now=&root;
else now=p->next[temp];
}
if(now->end){
node *tn=now;
while(tn!=NULL){
ans+=tn->end;
tn->end=0;
tn=tn->fail;
}
}
}
return ans;
}
五.经典例题
1.hdoj 2222 keywords search(简单模版题)
|
Problem Description In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Input First line will contain one integer means how many cases will follow by.
Output Print how many keywords are contained in the description.
Sample Input 1 5 she he say shr her yasherhs
Sample Output 3 |
题目分析:
就是问你所有关键词在文章里有多少个出现过,多次出现只对答案加1!
ac代码
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <malloc.h>
using namespace std;
const int maxkeywordlen=51;
const int maxstrlen=1000001;
char keyword[maxkeywordlen],str[maxstrlen];
int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x]
void init_charmapping(){
for(int i='a';i<='z';i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便.
charmapping[i]=i-'a';
}
}
struct node{
node *fail; //失败指针,此节点失配时将跳向fail所指节点
int end; //此值表示以此节点为结尾的单词个数
node *next[26]; //指向子节点
}root;
node *getnode(){ //构造 一个新结点并做好初始化,返回指向该节点的指针
node *newnode=(node *)malloc(sizeof(node));
newnode->end=0;
newnode->fail=NULL;
for(int i=0;i<26;i++) newnode->next[i]=NULL;
return newnode;
}
void insert(char *s){ //向ac自动机加入字符串s
int k=0,temp;
node* t=&root;
for(int i=0;s[i];i++){
temp=charmapping[s[i]];
if(!t->next[temp]) t->next[temp]=getnode();
t=t->next[temp];
}
t->end++;
}
void build_fail(){ //构造ac自动机的失败指针
queue<node *> q;
q.push(&root);
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++){
if(t->next[i]){
if(t==&root) t->next[i]->fail=&root;
else{
node *p=t->fail;
while(p!=NULL){
if(p->next[i]){
t->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) t->next[i]->fail=&root;
}
q.push(t->next[i]);
}
}
}
}
void free_trie(){ //释放ac自动机, 只留根节点
queue<node *> q;
for(int i=0;i<26;i++){
if(root.next[i]){
q.push(root.next[i]);
root.next[i]=NULL;
}
}
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++) if(t->next[i]) q.push(t->next[i]);
free(t);
}
}
int match(char *s){ //计算ac自动机中所有模式串在字符串s中出现的次数之和
node *now=&root;
int ans=0;
for(int i=0;s[i];i++){
int temp=charmapping[s[i]];
if(now->next[temp]) now=now->next[temp];
else{
node* p=now->fail;
while(p!=NULL&&p->next[temp]==NULL) p=p->fail;
if(p==NULL) now=&root;
else now=p->next[temp];
}
if(now->end){
node *tn=now;
while(tn!=NULL){
ans+=tn->end;
tn->end=0;
tn=tn->fail;
}
}
}
return ans;
}
int main(){
init_charmapping();
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",&keyword);
insert(keyword);
}
build_fail();
scanf("%s",&str);
printf("%d\n",match(str));
free_trie();
}
return 0;
} 2.hihocoder hiho218 Keywords Filter
我写了这道题的解题博客,点标题就能进去