c/c++语言开发共享[AC自动机][学习笔记]

用途

ac自动机适用于一类用多个子串在模板串中匹配的字符串问题。

也就是说先给出一个模板串，然后给出一些子串。要求有多少个子串在这个模板串中出现过。

kmp与trie树

其实ac自动机就是kmp与trie的结合版。或者说是在trie上进行的kmp算法。所以学会kmp和trie是学习ac自动机的基础。

对于上面那类问题。可以对于每个子串都用kmp算法在母串中匹配一次。但是复杂度就成了(n^2)

ac自动机

而对于这类问题，ac自动机的实现是先把所有的子串都挂到trie树上，然后在用母串去trie上匹配。

首先往trie上挂子串和普通的trie一样。就像这样

void add() {    int len = strlen(s + 1);    int now = 0;    for(int i = 1;i <= len;++i) {       if(!trie[now][s[i] - 'a']) trie[now][s[i] - 'a'] = ++tot;       now = trie[now][s[i] - 'a'];    }    val[now]++; }

然后就要建立失配指针。也就是建立起一张trie图，与trie树的区别是这是一张图。(废话)。和kmp类似。如果当前节点下面有x这个字符，那么x的失配指针就指向当前节点失配指针的x孩子。否则，当前节点的儿子就是当前节点失配指针的x孩子。

代码就像这样

void build() {    for(int i = 0;i < 26;++i) if(trie[0][i]) fail[trie[0][i]] = 0,q.push(trie[0][i]);    while(!q.empty()) {       int u = q.front();q.pop();       for(int i = 0;i < 26;++i) {          if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i],q.push(trie[u][i]);          else trie[u][i] = trie[fail[u]][i];       }    } }

查询，那么如何查询呢。其实也很简单，像在trie树上查询一样在这个trie图上查询母串。每查询到一个节点，就不断的沿着他的fail指针跳，然后加上跳到的节点的标记(用来标记当前节点是多少个子串的结尾的标记)。并且标记为访问过了，防止以后重复访问。

代码就像这样

int query() {    int now = 0;    int ans = 0;    int len = strlen(s + 1);    for(int i = 1;i <= len;++i) {       now = trie[now][s[i] - 'a'];       for(int j = now;j && val[j] != -1;j = fail[j]) ans += val[j],val[j] = -1;     }    return ans; }

其实ac自动机的用途非常广泛，并不是只能处理这一类问题。在各种题目中可以见到他的很多应用。