[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自动机的用途非常广泛,并不是只能处理这一类问题。在各种题目中可以见到他的很多应用。

上一篇:AC自动机学习笔记


下一篇:我理解的epoll(三)多线程模式下的ET