算法讲解：ac自动机及简单衍生

2018年8月31日 23:54 星期五

字号：小中大

AC自动机简介：

首先简要介绍一下AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。嗯没错，比如word文档等一系列带有查找功能的东西一般用的都是这种东西啦。要搞懂AC自动机，先得有字典树Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法，AC自动机是多模式串的字符匹配算法。至于什么有限状态自动机之类的，就是自动机理论的之后的事情了。嘛，在后面补了一下有限状态自动机的知识，有兴趣可以去下面看。

AC自动机前置技能： trie树和kmp。

trie树呢，是一种存储了一系列字符的树，每个节点存储一个字符，在一棵树的分支进行遍历，每次都会得到一个存储好的字符串。

假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们构建的树就是如下图这样的：

这样就可以看出，查找一个字符串，那就直接顺着这个串找下去就好了，唔，时间复杂度貌似是O（1）的

trie树的用途也非常多，在这里就先不展开分析了，一般用于字符串的存储，查询之类的，具体问题可以参考我的其他题解。

这是poj2001的代码，trie树裸题，可以作为参考。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int MAXN=3000000;
typedef long long ll;
char s[10005][31];
struct node
{
	int num;
	node* next[26];
	node()
	{
		memset(next,NULL,sizeof(next));
		num=0;
	}
};
node* root=new node();
void build(char str[])
{
	node* p=root;
	int len=strlen(str);
	for(int i=0;i<len;i++)
	{
		int index=str[i]-'a';
		if(p->next[index]==NULL)
		{
			p->next[index]=new node();
		}
		p=p->next[index];
		p->num++;
	}
}
void query(char str[])
{
	node* p=root;
	int len=strlen(str);
	for(int i=0;i<len;i++)
	{
		printf("%c",str[i]);
		int index=str[i]-'a';
		p=p->next[index];
		if(p->num==1)
		return;
	}
}
int main()
{
    int T;
    int n=0;
    while(scanf("%s",s[n])!=EOF)
	{
		build(s[n]);
		n++;
	}
	for(int i=0;i<n;i++)
	{
		printf("%s ",s[i]);
		query(s[i]);
		printf("\n");
	}
    return 0;
}

下一个内容，kmp。

kmp是一种字符串的算法，貌似现在的strstr就是用kmp重写的，用的最多的当然就是查找一个字符串中有没有给定的字串，位置和个数了

因为朴素的查找方法是O(n^2)的，其中由于进行了回溯，导致效率的下降，但问题在于，回溯过去的子串我们已经查找过了，能否保留查找的内容呢？答案当然是可以的。

我们可以用一个next数组来保存前缀的值，每次失配就直接导向失配的上一个子串位置，从而减少了不必要的匹配过程，其中，next数组的求解方式类似于动态规划，事实上就是动态规划的一种思想。在创建next数组的时候就相当于对本串进行一次kmp匹配。双指针扫两个串的两个点，同时前指针还有赋值的作用。

具体可以参照kmp的内容和代码，在此不做仔细讲解.

以下是poj3461查找一个字符串对另一个字符串的子串个数的代码，可以作为参考。

#include <iostream>
#include <cstring>
#include<cstdio>
using namespace std;
const int N = 1000002;
int nxt[N];
char S[N], T[N];
int slen, tlen;
void getNext()
{
	int j=0,k=-1;nxt[0]=-1;
	while(j<tlen)
	{
		if(k==-1||T[j]==T[k])
			nxt[++j]=++k;
		else
			k=nxt[k];
	}
}
int kmp()
{
	int i=0,j=0,ans=0;
	getNext();
	while(i<slen)
	{
		if(j==-1||S[i]==T[j])
		{
			i++;
			j++;
		}
		else
		{
			j=nxt[j];
		}
		if(j==tlen)
		{
			ans++;
			j=nxt[j];
		}
	}
	return ans;
}
int main()
{
 
    int n;
    scanf("%d\n",&n);
    while(n--)
	{
	scanf("%s",T);
	scanf("%s",S);
	slen=strlen(S);
	tlen = strlen(T);
	printf("%d\n",kmp());
	}
    return 0;
}

接下来就进入ac自动机的正题：

ac自动机就是一种多模的匹配算法了，刚刚前置技能都已经讲完了，就直击原理，ac自动机本质上就是一棵trie树，存储了一系列单词，但是和trie树不同的是，在每个节点中都存有一个fail指针，用于保存失配后所需要移动到的节点位置（是不是很眼熟，对了，就是kmp的next数组嘛）

既然我们知道了 AC自动机是用来做什么的，那么我们就来说一说怎么在 Trie上构造 AC自动机。

首先，我们看一下条转时的条件，如同 KMP算法一样， AC自动机在匹配时如果当前字符匹配失败，那么利用fail指针进行跳转。由此可知如果跳转，跳转到的串的前缀，必为跳转前的模式串的后缀。由此可知，跳转的新位置的深度一定小于跳之前的节点。所以我们可以利用 bfs在 Trie上面进行 fail指针的求解。

下面，是具体的构造过程（和KMP是一样的）。首先 root节点的fail定义为空，然后每个节点的fail都取决自己的父节点的fail指针，从父节点的fail出发，直到找到存在这个字符为边的节点（向回递归），将他的孩子赋值给寻找节点。如果找不到就指向根节点，具体参照代码：

#include <iostream>
#include <cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1000002;
char s[1000100];
int n;
struct node
{
    int cnt;
    node* next[26];
    node* fail;
    node()
    {
        cnt=0;
        fail=NULL;
        memset(next,NULL,sizeof(next));
    }
};
node *root;
void bfs()//通过bfs寻找fail指针的值
{
    node *p=root,*tmp,*son;
    queue<node*> q;
    q.push(p);
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        for(int i=0; i<26; i++)
        {
            son=tmp->next[i]; //队首元素的子节点
            if(son!=NULL)
            {
                p=tmp->fail; //p作为保存节点 表示类似kmp当前k的值
                while(p!=NULL)
                {
                    if(p->next[i]!=NULL)
                    {
                        son->fail=p->next[i];
                        break;
                    }
                    p=p->fail;
                }
                if(!p) son->fail=root;
                q.push(son);
            }
        }
    }
}
void insert() //和trie树一样的插入方式
{
    node *p=root;
    int len=strlen(s);
    for(int i=0; i<len; i++)
    {
        int index=s[i]-'a';
        //printf("%d\n",index);
        if(p->next[index]==NULL)
        {
            p->next[index]=new node();
        }
        p=p->next[index];
    }
    p->cnt++;
}
void query()
{
    int ans=0;
    node* p=root,*tmp;
    int len=strlen(s);
    for(int i=0; i<len; i++)
    {
        int index=s[i]-'a';
        while(p!=root&&p->next[index]==NULL) //kmp中的k=next[k]的相同思路
        {
            p=p->fail;
        }
        p=p->next[index];//下一节点
        if(p==NULL)//匹配失败 j=0
        {
            p=root;
        }
        tmp=p;
        while(tmp!=root) //与kmp不同，找寻所有满足子条件的节点。
        {
            if(tmp->cnt>=0)
            {
                ans+=tmp->cnt;
                tmp->cnt=-1;
            }
            else
                break;
            tmp=tmp->fail;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    int tt=0,T;
    scanf("%d",&T);
    while(T--)
    {
        root = new node();
        scanf("%d\n",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%s",s);
            //printf("%s\n",s);
            insert();
        }
        bfs();
        scanf("%s",s);
        query();
    }
    return 0;
}

时间复杂度分析：

对于Trie的匹配来说时间复杂性为：O(max(L(Pi))L(T))其中L串的长度函数，P是模式串，T是目标串。

对于 AC自动机来说时间复杂性为：O(L(T)+max(L(Pi))+m)气质m是模式串的数量。

对于 Trie 图来说时间复杂性为：O(L(T))在此的时间复杂性都是指匹配的复杂度。

对于构造的代价是 O(sum(L(Pi)))其中sum是求和函数。

嘛，因为学长说ac自动机太简单了（orz）所以要求我扩展一下ac自动机的内容：

trie图：

在讲tire图的时候，先科普一下有限状态自动机的知识：

有限状态自动机是具有离散输入和输出的系统的一种数学模型。

其主要特点有以下几个方面：

– (1)系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务。

– (2)我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串。

– (3)系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。

– (4)系统中有一个状态，它是系统的开始状态。

– (5)系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子。

形式定义

· 定义：有限状态自动机(FA—finite automaton)是一个五元组：

– M=(Q, Σ, δ, q0, F)

· 其中，

– Q——状态的非空有穷集合。∀q∈Q，q称为M的一个状态。

– Σ——输入字母表。

– δ——状态转移函数，有时又叫作状态转换函数或者移动函数，δ：Q×Σ→Q，δ(q,a)=p。

– q0——M的开始状态，也可叫作初始状态或启动状态。q0∈Q。

– F——M的终止状态集合。F被Q包含。任给q∈F，q称为M的终止状态。

用几句话来概括就是：

把问题的求解过程划分成离散的“状态”，并用一个有向图建立状态（结点）的迁移关系。
实现一个程序单位，在给定初始状态后，能够根据输入信息实现状态间的迁移，并可以在有限步骤后迁移到预定的“终态”。
在迁移的过程中，问题得到解决。//摘自网上

这就是有限状态自动机的理论了，那么为什么要讲到这里呢，嗯，是为了引出确定性有限状态自动机和不确定性有限状态自动机的区别

tire图，说起来就是比ac自动机多了一个确定性

确定性是什么？

非确定有限状态自动机与确定有限状态自动机的唯一区别是它们的转移函数不同。确定有限状态自动机对每一个可能的输入只有一个状态的转移。非确定有限状态自动机对每一个可能的输入可以有多个状态转移，接受到输入时从这多个状态转移中非确定地选择一个。

trie图中会有补边这样一个机制，而且在根节点保存了所有字典中的字符从而满足了trie图的确定性：

也就是说，每一个确定的输入字符都会给你一个确定的状态节点

在ac自动机和trie图中，区别就是ac自动机失配后可能需要进行多次转移，但trie图只需要一次转移

Trie图是AC自动机的确定化形式，即把每个结点不存在字符的next指针都补全了。这样做的好处是使得构造fail指针时不需要next指针为空而需要不断回溯。

比如构造next[cur][i]的fail指针，cur为父节点，next[cur][i]为cur的儿子结点，如果是AC自动机，如果父亲结点tmp(tmp是cur的一份拷贝）的next[fail[tmp]][i]不存在时，需要让tmp不断回溯(即tmp = fail[tmp])，直到next[fail[tmp]][i]不为空时，才让fail[next[cur][i]] = next[fail[tmp]][i]。

如果是Trie图，那么直接让fail[next[cur][i]] = next[fail[cur]][i]就可以了，因为Trie图已经补全了next指针。

嘛 ac自动机和trie图中的区别网络中众说纷纭，不管了，具体名词可能有所区别，但思想是不会变的

由于其实和ac自动机使用上几乎没有区别，实战上使用次数不多，以下就发一个代码作为trie图的总结。（在敲模板时发现trie图要比ac自动机好写一点，嘛，不过根据先入为主的原则，还是ac自动机要顺手吧）

#include <iostream>
#include <cstring>
#include <queue>
 
 
using namespace std;
 
struct Trie
{
    int flag;
    struct Trie* behind;
    struct Trie* next[26];
};
 
int main()
{
    int n;
    char s[100001];
    cin >> n;
    Trie* root = new Trie;
    for (int i = 0; i < 26; i++)
    {
        root->next[i] = NULL;
    }
    root ->behind = NULL;
    root ->flag = 0;
    while (n--)
    {
        cin >> s;
        Trie* p = root;
        for (int i = 0; s[i]!='\0'; i++)
        {
            int j = s[i] - 'a';
            if (!p->next[j])
            {
                Trie* q = new Trie;
                q->flag = 0;
                for (int k = 0; k < 26; k++)
                {
                    q->next[k] = NULL;
                }
                q ->behind = NULL;
                p->next[j] = q;
            }
            p = p->next[j];
        }
        p->flag = 1;
    }
 
    queue<Trie*> Q;
    root->behind = root;
    for (int i = 0; i < 26; i++)// 和ac自动机的差别哦，初始状态补边
    {
        if(!root->next[i])
        {
            root->next[i] = root;
        }
        else
        {
            root->next[i]->behind = root;
            Q.push(root->next[i]);
        }
    }
    while(!Q.empty())
    {
        Trie *p = Q.front();
        Trie *q = p->behind;
        Q.pop();
        for (int i = 0; i < 26; i++)
        {
            if(!p->next[i])
            {
                p->next[i] = q->next[i];
            }
            else
            {
                p->next[i]->behind = q->next[i];
                Q.push(p->next[i]);
            }
        }
    }
    char article[1000001];
    Trie* p = root;
    cin >> article;
    bool tag = false;
    for (int i = 0; article[i]!='\0'; i++)
    {
        int j = article[i] - 'a';
        p = p->next[j];
        if(p->flag == 1)
        {
            tag = true;
            cout << "YES" <<endl;
            break;
        }
    }
    if(tag == false)
        cout << "NO" <<endl;
    return 0;
}

fail树：

因为本人太弱嘛，只能初步简单的提一下fail树及其应用。

fail树呢，是将ac自动机（trie图）中的所有fail指针反向，但是不管是Trie图还是AC自动机，它们的fail指针的指向都是一模一样的。

我们可以发现，因为一个点只会引出一个fail指针，所以反向之后就证明任意一个点只会有一个点指向他，那就说明这个点的父亲节点只有一个，可知该图是一棵树。我们称之为fail树

fail树的应用：

如果有n个字符串，所有字符串的长度加起来不超过，有m个查询，要查询第x个字符串在第y个字符串中出现了多少次。

如果是使用AC自动机查询，可以直接对字符串构建AC自动机，然后让y去走AC自动机，对于走过的结点，把其权值加1。那么要查询x在y中出现了多少次，便要从底层开始，顺着fail指针把权值上传。然后只要查询x结点的权值是多少就知道x在y中出现了多少次。每次查询的复杂度是O(tot+len[y]),其中tot是AC自动机的结点总数。很多oj上就会直接把ac自动机的方法卡掉

如果是使用Fail树进行查询，那么只要查询所有子结点的权值和就好了，子结点的权值和可以使用dfs序和树状数组来维护。然后同样让有去走AC自动机，将走过的结点的权值加1，只不过现在是用树状数组来维护权值。那么要查询x在y中出现了多少次，只要进行一次区间查询就可以了，即只要查询x结点的所有子结点就好了（根据fail树的性质），因为其dfs序号是连续的，所以是一次区间查询。可以将查询按照y排序，然后对具有相同y的查询一起查询。每次查询时间复杂度是O(len[y]+log(tot))。