AC 自动机

简介 #

AC 自动机不是能自动 AC 的机器，而是一种著名的多模式串匹配算法.

问题 #

给定 $n$ 个模式串 $A_1\sim A_n$ 和一个长为 $m$ 的主串 $S$，问有多少个模式串在 $S$ 中出现过.

假设 $n$ 个模式串互不相同，且字符串中仅含小写字母.可以考虑枚举 $S$ 的所有子串并进行判断.

int n, ans;
string A[], S;

int m = S.size();
for(int l = 0; l < m; l ++) {
    for(int r = l + 1; r < m; r ++) {
        string substr = S.substr(l, r - l + 1); // substr = S[l...r]
        for(int i = 1; i <= n; i ++) {
            if(substr == A[i]) {
                ans ++;
            }
        }
    }
}
cout << ans;

暴力算法（$\textcolor{red}{×}$）	AC 自动机（$\textcolor{green}{√}$）
$O(n^3)$	$O(n+m)$

原理 #

Under Construction ...

模板 #

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

void insert(char *s) {
    int u = 0;
    for(int i = 1; s[i]; i ++) {
        if(!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++ tot;
        u = tr[u][s[i] - 'a'];
    }
    e[u]++;
}

int query(char *t) {
    int u = 0, res = 0;
    for(int i = 1; t[i]; i ++) {
        u = tr[u][t[i] - 'a'];
        for(int j = u; j && e[j] != -1; j = fail[j])
            res += e[j], e[j] = -1;
        }
    return res;
}