AC自动机

前置知识

使用场景

AC自动机是一种著名的多模式匹配算法。

可以完成类似于KMP算法的工作,但是由单字符串的匹配变成了多字符串的匹配。

一般来说,会有很多子串,和一个母串。问题常是求字串在母串中的出现情况(包括位置,次数,等等)

算法思想与流程

我在
Trie树
一文中提到过这样一句话

而AC自动机的核心就在于通过对Trie树进行处理,使得在处理母串的信息时可以快速的进行状态转移。

可以类比KMP的算法流程,但是这不重要

例如子串有
aa
,
ab
,
abc
,
b
。母串为
ababcba

由于我们是通过母串进行状态转移,所以需要先把所有字串的信息搞定

我们可以先处理子串,建一棵Trie树

明显,对于一个字串的匹配,是不可能在树上一路到底的,所以要构建匹配失败时的回退机制。也就是需要构建失配指针。

那么失配指针是干什么的?也就是用来在
Trie
树上向上跳,找到可以转移的一个节点,进行状态转移。

假如我现在在3号节点,并且我下一个需要转移的状态是
b
,很明显,我此时应该回退到1节点(其上第一个可以通过
b
转移的节点)并转移到4节点。如果再来一个
b
,也只能向上走到0号节点,然后转移到2号节点。

如此看来,我们完全可以暴力向上跳找到可转移的状态或者到达根为止。但是,这明显不够优秀,我们完全可以继承其子节点的。也就是继承
fail
的子节点。使得不需要暴力向上跳。

那说了半天,
fail
到底指向啥?

假设父节点到当前节点转移的状态为
x
,父节点之上第一个可以通过
x
转移到下一个节点的节点为
u
,则
fail
指向
u
通过
x
转移过后的节点。

其实还有另一种解释的方法

fail
指向
p
代表当前串的最长已知后缀。

例如
aa
的最长已知后缀为
a
,所以 3号节点的
fail
指向 1号节点;
abc
的最长已知后缀为空,所以
5
号节点的
fail
指向根节点。

好混乱,我尽力了……

那么核心代码……就是利用
BFS
来处理

void procFail(int * q) {
    int head(0), tail(0);
    for (int i(0); i < 26; ++i) {
        if (kids[0][i]) q[tail++] = kids[0][i];
    }

    while (head ^ tail) {
        int x = q[head++];
        for (int i(0); i < 26; ++i) {
            if (kids[x][i]) {
                fail[kids[x][i]] = kids[fail[x]][i];
                q[tail++] = kids[x][i];
            } else kids[x][i] = kids[fail[x]][i];
        }
    } // procFail end
}

注意事项
:一般来说,把
0
号作为根节点会比较方便。反正
0
上不可能有信息保存。

插入部分我就不需要讲了

匹配的判断

如何判断当前状态有没有匹配任何一个字串,只需要不断向上跳
fail
,看跳到的节点是不是代表着字串。

拿模板:
【模板】AC 自动机(简单版) - 洛谷
为例。

插入的时候在最后标记一下有没有匹配:

void insert(string &s) {
    int p(0);
    for (int c : s) {
        if (!kids[p][(c -= 'a')]) kids[p][c] = ++usage;
        p = kids[p][c];
    }
    ++cnt[p];
}

在匹配的时候暴力跳就是了:

int ACMatch(string & s) {
    int p(0), ans(0);
    for (int c : s) {
        p = kids[p][(c -= 'a')];
        for (int t(p); t && ~cnt[t]; t = fail[t]) {
            ans += cnt[t], cnt[t] = -1;
        }
    }
    return ans;
}

由于每一个串只能匹配一次,所以这里采用的清空的策略。并且标记清空,以免重复搜索。

失配树的应用

就拿模板题来说吧:
【模板】AC 自动机(二次加强版) - 洛谷

他是要求所有字串的出现情况。

那么,我们先把每一个到达的状态计数。再通过
fail
指针向上跳求和。

但毕竟不能每一个节点都暴力跳,所以考虑在
fail
树上求和。

但是,我们不是有一个
q

BFS
吗?其中的
fail
是有序的:对于一个节点
x
,其
fail
一定在
x
之前被遍历到。

所以我们直接使用
q
即可。

那么合起来大概也就是这样:

inline void ACMatch(string &s) {
    int p(0);
    for (char c : s) {
        p = kids[p][c - 'a'];
        ++cnt[p];
    }
}

inline void ACCount(int * q) {
    for (int i = usage; i; --i) {
        cnt[fail[q[i]]] += cnt[q[i]];
    }
}

但是每一个特定的字串出现的次数呢?

在插入时记住字串对应的节点,输出即可。

void insert(string &s, int i) {
    int p(0);
    for (int c : s) {
        if (!kids[p][(c -= 'a')]) kids[p][c] = newNode();
        p = kids[p][c];
    }
    pos[i] = p;
}


inline void ACOutput(int n) {
    for (int i = 1; i <= n; ++i) {
        cout << cnt[pos[i]] << '\n';
    }
}


有这么一道题:

很明显,对于每一个位置,我们需要清理能匹配到的最长长度,所以我们需要预处理出最长长度:

inline void ACprepare(int * q) {
    for (int i = 1; i <= usage; ++i) {
        len[q[i]] = max(len[q[i]], len[fail[q[i]]]);
    }
}

在清理时:

inline void ACclean(string &s) {
    int p(0);
    for (unsigned i(0), ie = s.size(); i < ie; ++i) {
        p = kids[p][discrete(s[i])];
        if (len[p]) for (unsigned j = i - len[p] + 1; j <= i; ++j)
            s[j] = '*';
    }
}

由于是引用的字符串,所以可以直接修改。

对状态的理解

在我们考试的时候有这么一道题:

这道题说难也难,说不难也不难。主要是看对于
AC自动机
状态转移的理解到不到位。

在匹配过程中,如果匹配到了出现的
w
,那么就要回到
len(w)
个状态前,继续匹配下一个字符。

很明显,需要用栈,并且由于需要一次弹出多个,所以最好用手写的栈。

核心代码如下:

string sub, pat;
cin >> sub >> pat;
insert(sub), procFail(Q);

int p = 0;
for (int i(0), ie = pat.size(); i < ie; ++i) {
    p = kids[cps[ci]][pat[i] - 'a'];
    cps[++ci] = p, ccs[ci] = pat[i];
    if (match[p]) ci -= sub.size();
}

for (int i = 1; i <= ci; ++i) {
    putchar(ccs[i]);
}

这里没有用到
fail
,那么为什么还要构建失配树?

这是个好问题,因为,构建失配树的过程不仅仅构建了失配树,同时还令节点继承了其
fail
的子节点,所以需要构建的过程。


最后附上模板题
【模板】AC 自动机(二次加强版) - 洛谷
的代码:

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
const int N = 1e6 + 7;

int res[N], cnt[N], pos[N];
class ACAutomaton {
private:
	int kids[N][26];
	int fail[N], id[N], usage;
public:
	ACAutomaton() : usage(0) {
	}
	
	inline int newNode() {
		fill_n(kids[++usage], 26, 0);
		cnt[usage] = fail[usage] = id[usage] = 0;
		return usage;
	}
	
	void insert(string &s, int i) {
		int p(0);
		for (int c : s) {
			if (!kids[p][(c -= 'a')]) kids[p][c] = newNode();
			p = kids[p][c];
		}
		pos[i] = p;
	}
	
	void procFail(int * q) {
		int head(0), tail(0);
		for (int i(0); i < 26; ++i) {
			if (kids[0][i])
				fail[kids[0][i]] = 0, q[tail++] = kids[0][i];
		}
		
		while (head ^ tail) {
			int x = q[head++];
			for (int i(0); i < 26; ++i) {
				if (kids[x][i]) {
					fail[kids[x][i]] = kids[fail[x]][i];
					q[tail++] = kids[x][i];
				} else kids[x][i] = kids[fail[x]][i];
			}
		} // procFail end
	}
	
	void debug() {
		for (int i = 0; i <= usage; ++i) {
			printf("node %d (cnt %d) fail to %d:\n\t", i, cnt[i], fail[i]);
			for (int j(0); j < 26; ++j) {
				printf("%d ", kids[i][j]);
			} puts("");
		}
	}
	
	inline void ACMatch(string &s) {
		int p(0);
		for (char c : s) {
			p = kids[p][c - 'a'];
			++cnt[p];
		}
	}
	
	inline void ACCount(int * q) {
		for (int i = usage; i; --i) {
			cnt[fail[q[i]]] += cnt[q[i]];
		}
	}
	
	inline void ACOutput(int n) {
		for (int i = 1; i <= n; ++i) {
			cout << cnt[pos[i]] << '\n';
		}
	}
	
	void clear() {
		usage = -1;
		newNode(); // clear 0
	}
} ac;

int Q[N];
string s; 

int main() {
	cin.tie(0)->sync_with_stdio(false);
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> s;
		ac.insert(s, i);
	} ac.procFail(Q);
	
	cin >> s;
	ac.ACMatch(s);
	ac.ACCount(Q);
	ac.ACOutput(n);
	return 0;
}

差不多了……下课

标签: none

添加新评论