KMP 和 AC 自动机

 

你现在有两个字符串 和 ，长度分别为 和 。你现在要求 串作为 串的子串时，出现的位置。

暴力匹配是非常容易给你卡成复杂度 的，所以我们要用一个非常厉害但难想的算法：KMP算法。

KMP

暴力匹配的算法因为在某一个地方失配了之后，要回溯到开头的下一位，就浪费了很多时间。而 KMP 算法就利用了字符串的最长公共前后缀，完美地避免了在主串 的回溯问题。

于是我们就可以考虑，如果在某一个位置失配了，就提取之前匹配的部分，找到它的最长公共前后缀（就是一个字符串最长的相同的前、后缀，例如串 的最长公共前后缀就是 ，串 的最长公共前后缀就是 ，串 的最长公共前后缀就是 ），因为这两个部分是相同的，所以可以直接从这一位开始匹配。

例子：

文本串 ：

模式串 ：，：

对于 ：

• 第一次匹配：在 处失配，因为 串无公共前后缀，所以让 。
• 第二次匹配：在 处匹配，则结束。

对于 ：

• 第一次匹配：在 处失配，因为之前成功匹配的 串有最长公共前后缀 ，则让 ，继续匹配。
• 第二次匹配：在 处失配。。而 串无公共前后缀，则让 。
• 第三次匹配：在 处失配。因为空串无公共前后缀，则让 。
• 第四次匹配：在 处匹配。结束。

如上述例子，我们可以利用之前成功匹配的串的最长公共前后缀，让 指针避免回溯。这样我们的时间复杂度就可以控制在 。

那么我们该如何获取对于模式串的每一个 ，串 的 部分的最长公共前后缀呢？

---

我们先把串 的 部分的最长公共前后缀记为 。假设我们知道了对于 的 值，如何求 ？

• 如果 ，那么 。

• 如果 ，则 ，继续判断，直到匹配成功之后 或是匹配失败到 为止。

有没有发现，这个思路和 KMP 求 串在 串中的匹配很像？思路非常相似。

于是，根据这个，我们就可以得出求出 数组的函数：

void getnxt(){
    for(int i=2,j=0;i<=m;i++){
        while(j&&t[i]!=t[j+1]) j = nxt[j];
        if(t[i] == t[j+1]) j++;
        nxt[i] = j;
    }
}

---

而其实上面这个代码，其实就是 数组的自我匹配。而求出 串在 串中出现的位置就可以用以下函数：

void solve(){
    for(int i=1,j=0;i<=n;i++){
        while(j&&s[i]!=t[j+1]) j = nxt[j];
        if(s[i] == t[j+1]) j++;
        if(j == m){
            cout<<i-m+1<<'\n';
        }
    }
}

那么 KMP 就这样，就讲完了！

之后我们开始将用 KMP 实现的自动机：AC自动机！

AC 自动机

AC 自动机和 KMP 类似，不过 AC 自动机是实现多模式串和一个文本串的匹配的。

我们做 AC 自动机的思路就是：将这些模式串全部放到 Trie 树上，然后建立回跳边和转移边，最后在这个自动机上遍历即可。

我们首先建立一群模式串的 Trie 树：

之后我们开始建回跳边：

我们定义某节点的回跳边是该节点的父亲的回跳边指向的点的儿子。

有点绕？画个图解释一下：

注意，这里的从父亲连向儿子的边所对应的字母都必须是相同的。

于是乎，我们可以把那棵树上所有的回跳边全部连起来：

我们可以发现，这个回跳边其实就是当前节点的最长后缀！

就相当于，如果我们到了到了某个点都是匹配的，我们就可以沿着这些回跳边，一直查找他的后缀。因为是他的后缀所以也是匹配的。可以做到不重不漏。非常神奇。

那么我们在遍历某节点的 个儿子的时候，若该儿子存在，那么就以它的儿子为起点连接儿子的回跳边。

那如果某个儿子不存在呢？

---

我们来介绍另外一种边：转移边。某个节点的转移边则指向当前节点的回跳边所指向的儿子。它少了个什么？少了一个爹。

注意：这里把转移边定义为了 ，是因为转移边就是 对于字母 的转移边所指的节点 的最短路。如果有真实的从 连向 的边，那么就不要连转移边。如果我们想从点 出发走边权为 的边的话，我们完全没有必要先跳回跳边再走边权为 的边。直接建一条转移边就可以从 走边权为 的边了。

于是我们就可以写出建 AC 自动机的代码：

void buildacam(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(ch[0][i]) q.push(ch[0][i]);
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(ch[u][i]) ne[ch[u][i]] = ch[ne[u]][i], q.push(ch[u][i]);
            else ch[u][i] = ch[ne[u]][i];
        }
    }
}

---

现在，我们要用 AC 自动机求有多少个模式串在文本串中出现过。我们该如何使用这个 AC 自动机？

我们可以搞一个指针 ，最开始在自动机的根部，然后让它跟着模式串在自动机里面走。我们只能让他走树边或是转移边，不能让他回退。

指针每到一个点，就新建一个指针 ，最初指向 。然后让 指针按照回跳边回跳到根。如果在路上遇到了某个模式串的末尾，就把它取走。答案 。（意思是后面再遍历到这个点的时候就不 了。）

可以用上面的自动机，把转移边连完了之后带入一个文本串验证一下。

int ans = 0;
void getans(){
    int now = 0;
    for(int i=1;i<=n;i++){
        int alp = s[i] - 'a';
        now = ch[now][alp];
        for(int j=now;j&&(cnt[j]!=-1);j=ne[j]){
            ans += cnt[j], cnt[j] = -1;
            // 把值赋为-1是为了剪枝，因为后面再扫到这个点的时候答案没了，回跳边还只有1条。
        }
    }
}

类似的问题：

有 个由小写字母组成的模式串以及一个文本串 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 中出现的次数最多。

这种问题与上面的问题思路差不多，只需要插入时将最后的位置 在 上对应的值为插入的串的编号，最后统计时只要这个地方有编号就将此地答案 ，最后取最大值即可。

void insert(int iidx){
    int p = 0;
    for(int i=1;i<=n;i++){
        int alp = s[iidx][i] - 'a';
        if(ch[p][alp]) p = ch[p][alp];
        else ch[p][alp] = ++idx, p = idx;
    }
    cnt[p] = iidx;
}
...
int ans[MAXN], maxans = 0;
void getans(){
    int p = 0;
    for(int i=1;i<=n;i++){
        int alp = s2[i] - 'a';
        p = ch[p][alp];
        for(int j=p;j;j=ne[j]){
            if(cnt[j]){
                ans[cnt[j]] ++;
                maxans = max(maxans, ans[cnt[j]]);
            }
        }
    }
}
void solve(){
    for(int i=1;i<=t;i++){
        cin>>(s[i]+1);
        n = strlen(s[i]+1);
        insert(i);
    }
    cin>>(s2+1);
    n = strlen(s2+1);
    buildacam();
    getans();
    ...
}

---

应用：ACAM + 一般DP

P3041

Bessie 在玩一款游戏，该游戏只有三个技能键 A，B，C 可用，但这些键可用形成 种特定的组合技。第 个组合技用一个字符串 表示。

Bessie 会输入一个长度为 的字符串 ，而一个组合技每在 中出现一次，Bessie 就会获得一分。 在 中出现一次指的是 是 从某个位置起的连续子串。如果 从 的多个位置起都是连续子串，那么算作 出现了多次。

若 Bessie 输入了恰好 个字符，则她最多能获得多少分？

这道题可以先把这些串插进一个 ACAM 里面，然后给是这个字符串结尾的节点的 加上 。

然后我们可以设 DP 状态： 表示现在 Bessie 输入了第 个字符，她现在输入的字符导致指针走到了 ACAM 的 号节点所能取得的最多的分数。

然后我们考虑转移：如果存在一条边 ，那么就可以转移：。

并且注意：最开始要 memset dp 数组为负无穷，然后设置 。

最后取 即可。

类似的题目：P4052

应用：ACAM + 数位 DP

接下来我讲一道数位 DP 和 ACAM 的结合应用：

​ 求 中，任取两个数字组成的有序对，十进制表示的最长公共子串长度之和。

​ 具体来说，令 表示数字 对应的不包含前导 的十进制字符串， 表示字符串 与 的最长公共子串， 表示字符串 的长度。你需要计算：

$$\displaystyle\sum_{1\le i\le n}\sum_{1\le j\le n}\text{len}(\text{LCS}(\text{str}(i), \text{str}(j)))$$

​ 其中，，时间限制 秒。

​ ——来自某道在 考的神秘联考题

这道题因为 只有 ，于是就可以考虑枚举 ，算每一个 对答案的贡献。这样我们就要要求算后面那个 的时候时间复杂度要尽量小。

因为这些数他最大也只有 位，我们就可以在枚举 的时候，把 的所有子串全部插进一个 ACAM 里面。我们容易发现，当你拿一个文本串去和 ACAM 里的模式串匹配的时候，这两个串的 就是指针走过的节点的深度的最大值。然后求 的过程可以使用数位 DP 来做。

具体地说，我们可以再枚举 和 的 ，因为最多也只到 ，所以无伤大雅。对于每一个 ，分别数位 DP 求：和 的 长度为 的小于 的数 到底有多少个。设 表示：现在枚举到了从低到高的第 位，现在在 ACAM 的编号为 的点上，当前的最大 为 ，是否含有前导 ，是否以抵达枚举的上界 （这两项是数位 DP 的基本操作）。

然后终止条件就是当 的时候，判断一下 是否等于当前枚举的 ：。如果等于返回 ，否则返回 。然后其他的统计就是数位 DP 的基本操作。记得最后给答案算贡献时要乘上 ，否则会出错！

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 75;
const int A = 10;
const int M = 7;
typedef long long ll;
ll mem[M][N][M];
namespace ACAM{
    int ch[N][A], ne[N], dep[N], idx;
    void clear(){
        memset(ch, 0, sizeof ch);
        memset(ne, 0, sizeof ne);
        memset(dep, 0, sizeof dep);
        idx = 0;
    }
    int ins[M], inslen;
    void insert(){
        int p = 0;
        for(int i=1;i<=inslen;i++){
            int alp = ins[i];
            if(ch[p][alp]) p = ch[p][alp];
            else ch[p][alp] = ++idx, dep[idx] = dep[p]+1, p=idx;
        }
    }
    void buildacam(){
        queue<int>q;
        for(int i=0;i<A;i++){
            if(ch[0][i]) q.push(ch[0][i]);
        }
        while(q.size()){
            int u = q.front();
            q.pop();
            for(int i=0;i<A;i++){
                if(ch[u][i]) ne[ch[u][i]] = ch[ne[u]][i], q.push(ch[u][i]);
                else ch[u][i] = ch[ne[u]][i];
            }
        }
    }
}

using namespace ACAM;
int n;
int num[M], len;
int nbit[M], nlen;
int lcs;
ll ans = 0;
int dp(int bit, int p, int nowlcs, int is0, int islim){
    if(bit==0) return nowlcs == lcs;
    if(nowlcs > lcs) return 0;
    if(!is0 && !islim && (mem[bit][p][nowlcs]!=-1))
        return mem[bit][p][nowlcs];
    int res = 0, lim = (islim?nbit[bit]:9);
    for(int i=0;i<=lim;i++){
        if(i==0&&is0){
            res += dp(bit-1, p, nowlcs, is0, islim & (i==lim));
        }else{
            res += dp(bit-1, ch[p][i], max(nowlcs, dep[ch[p][i]]), is0 & (i==0), islim & (i==lim));
        }
    }
    if(!is0 && !islim) mem[bit][p][nowlcs] = res;
    return res;
}
void solve(int now){
    clear();
    len = 0;
    for(int i=now;i;i/=10) num[++len] = i%10;
    for(int l=1;l<=len;l++){
        for(int r=l;r<=len;r++){
            inslen = r-l+1;
            for(int k=l;k<=r;k++){
                ins[r-k+1] = num[k];
            }
            insert();
        }
    }
    buildacam();
    //枚举：ＬＣＳ长度
    for(lcs=1;lcs<=len;lcs++){
        memset(mem, 0xff, sizeof mem);
        ans += ll(lcs) * dp(nlen, 0, 0, 1, 1);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    nlen = 0;
    for(int i=n;i;i/=10) nbit[++nlen] = i%10;
    for(int i=1;i<=n;i++) solve(i);
    cout<<ans;
    return 0;
}

时间复杂度：。（虽然我也不知道是啥，但是能过）

类似的题目：P3311

比较���的类型：ACAM + 图论

P2444

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 为病毒代码段，那么一个可能的无限长安全代码就是 。如果 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码。

这道题可以先造出这些串的 ACAM，然后观察它的性质：我们设 ACAM 上的某个表示的字符串存在病毒代码的点为病毒点，那么存在无限长的安全代码当且仅当这个 ACAM 上存在一个不经过病毒点的环。

于是我们可以在造 ACAM 的同时预处理出哪些点是病毒点，然后从根开始跑一遍 DFS 查找有无符合上述条件的环即可。

具体地说，我们定义一个状态数组 表示每个点的状态：若值为 ，表示这个点没有被 DFS 到过；若值为 ，表示现在正在 DFS 这个点或从这个点连出去的点；若值为 ，则表示这个点已经被遍历过了。根据定义，就要刚刚开始遍历这个点的时候设置这个点的 值为 ，把这个点连出去的点遍历完了之后就设这个点的 为 。

然后 DFS 时，先判断终点是否为病毒点。如果是则 continue。若不是，则判断其状态。若其为 ，则继续深搜。若其为 ，那么就可以设置答案为 true 了。DFS 完了之后即可输出。

DFS 代码：

int stat[N];
int ans = 0;
void dfs(int x){
    stat[x] = 1;
    for(int i=0;i<A;i++){
        if(ans) return ;
        int v = ch[x][i];
        if(cnt[v]) continue;
        // 注意在建 ACAM 的函数里面不要忘记加 cnt[ch[u][i]] |= cnt[ne[ch[u][i]]]
        if(stat[v] == 0){
            dfs(v);
        }else if(stat[v] == 1){
            ans = 1;
            return ;
        }
    }
    stat[x] = 2;
}

另一个应用：ACAM + 线段树优化，但是毒瘤题

SP9941 / UVA1502

首先考虑最简单的 DP：我们设 为考虑字符串 时，必须选上串 的权值最大值。设 为字符串 对应的权值。

于是我们有转移方程为：

$$dp_{i} = \displaystyle\max_{1\le j<i \land str_j 为 str_i 的子串}\{dp_j + val_i\}$$

最暴力的方法肯定就是枚举 ，KMP 判断串 是否为串 的子串。时间复杂度 ，直接爆炸飞上天。

于是要优化这个 DP。现在的目标就是要快速找到字符串编号小于 且为 的子串的字符串，并且还要快速查找它们的 DP 值。

而这个时候，因为有多个字符串，并且涉及到子串匹配问题，我们可以用 AC 自动机来试着解决。

我们现在考虑一个字符串的子串在 AC 机上面有什么性质：假设 串为 串的子串， 串在 AC 机上代表的点为 ， 串在 AC 机上代表的点为 。我们称在 AC 机上连接点 和点 的链为 的根链。

于是，我们发现，在 Fail 树上， 的子树中一定包含 的根链中的某一个点！

考虑为什么会这样。因为我们知道 Fail 树上，点 一定为 在 Fail 树上的任意后代的一个后缀。而如果这些后代中有一个是 的根链上的某一个点，那么就相当于是字符串 就是字符串 的某个前缀的后缀，也就是字符串 的子串了。

于是，我们就可以想：对于在 AC 机上的每一个点，设置一个点权，表示这个点对应的字符串如果你选了，那么你会获得的最大权值。因为你要选某个字符串，所以相当于你选了这个字符串和这个字符串的所有前缀。所以就每次在 AC 机上跑完这个字符串，得到了这个字符串在 AC 机上面代表的点 之后，给 在 Fail 树上面的子树（包含 本身）内的点，让它们的点权和这个串的 值取 。然后查询就是边在 AC 机上面跑边查询这个点的权值。

这个就可以用 DFS 序加上线段树维护。具体地说，就是首先把所有字符串塞到一个 AC 机里面，然后就得到了一个 Fail 数组。然后再利用这个数组造一棵 Fail 树。然后再求出它的 DFS 序。目的就是：因为是给某个点的子树 上某一个值，求出 DFS 序会使这个修改操作是连续的。于是就可以用线段树维护了。然后就是对于字符串 ，先跑 AC 机，每跑到一个点就查询一下这个点的权值，查询到前面的 最大值了之后再把它加上一个 就变成了 。最后再对于串 在 AC 机上代表的点 ，让 在 Fail 树上的子树内的所有点的点权全部和 取 ，也就可以转化为线段树的修改操作了。于是这道题就做完了

（我不知道是我不会卡常还是怎么回事，这道题似乎用不了 cin，我的代码必须用 scanf 才能通过。）

Code（封装封装再封装版本）:

#include<bits/stdc++.h>
using namespace std;
const int N = 20020;
const int M = 300020;
const int A = 26;
char s[M], sall[M];
int n, wordval[N];
int L[N], R[N], len;
namespace ACAM{
    int ch[M][A], ne[M], idx;
    void insert(){
        len = strlen(s+1);
        int p = 0;
        for(int i=1;i<=len;i++){
            int alp = s[i] - 'a';
            if(ch[p][alp]) p = ch[p][alp];
            else ch[p][alp] = ++idx, p = idx;
        }
    }

    void buildacam(){
        queue<int> q;
        for(int i=0;i<A;i++){
            if(ch[0][i]) q.push(ch[0][i]);
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=0;i<A;i++){
                if(ch[u][i]) ne[ch[u][i]] = ch[ne[u]][i], q.push(ch[u][i]);
                else ch[u][i] = ch[ne[u]][i];
            }
        }
    }

    void acamclear(){
        memset(ch, 0, sizeof ch);
        memset(ne, 0, sizeof ne);
        idx = 0;
    }
}
using namespace ACAM;

void transfer_string(int id){
    for(int i=1, j=R[id-1]+1; i<=len; i++, j++){
        sall[j] = s[i];
    }
    L[id] = R[id-1] + 1;
    R[id] = R[id-1] + len;
}

namespace Graph{
    struct Edge{
        int to, nxt;
    }edge[M<<1];
    int h[M], cnt;
    void _add(int u, int v){
        edge[++cnt] = {v, h[u]};
        h[u] = cnt;
    }
    void add(int u, int v){
        _add(u, v), _add(v, u);
    }
    int dfn[M], dfnidx, endfn[M];
    void make_failtree(){
        for(int i=1;i<=idx;i++) add(ne[i], i);
    }
    void dfs(int x, int fa){
        dfn[x] = ++dfnidx;
        for(int i=h[x];i;i=edge[i].nxt){
            int v = edge[i].to;
            if(v==fa) continue;
            dfs(v, x);
        }
        endfn[x] = dfnidx;
    }
    void graphclear(){
        memset(h, 0, sizeof h);
        cnt = dfnidx = 0;
    }
}
using namespace Graph;


namespace Max_SegTr{
    int val[M<<2], lazy[M<<2];
    void pushup(int x){
        val[x] = max(val[x<<1], val[x<<1|1]);
    }
    void modify(int x, int w){
        val[x] = max(val[x], w);
        lazy[x] = max(lazy[x], w);
    }
    void pushdown(int x){
        if(lazy[x]){
            modify(x<<1, lazy[x]);
            modify(x<<1|1, lazy[x]);
            lazy[x] = 0;
        }
    }
    void change(int x, int l, int r, int ql, int qr, int w){
        if(ql<=l&&r<=qr){
            modify(x, w);
            return ;
        }
        pushdown(x);
        int mid = (l+r)>>1;
        if(ql<=mid) change(x<<1, l, mid, ql, qr, w);
        if(qr>mid) change(x<<1|1, mid+1, r, ql, qr, w);
        pushup(x);
    }
    int query(int x, int l, int r, int pos){
        if(l==r){
            return val[x];
        }
        pushdown(x);
        int mid = (l+r)>>1;
        if(pos <= mid) return query(x<<1, l, mid, pos);
        else return query(x<<1|1, mid+1, r, pos);
    }
    void segtrclear(){
        memset(val, 0, sizeof val);
        memset(lazy, 0, sizeof lazy);
    }
}
using namespace Max_SegTr;

int ans = 0;

void solve_eachstring(int id){
    int p = 0;
    int nowval = 0;
    for(int i=L[id];i<=R[id];i++){
        int alp = sall[i] - 'a';
        p = ch[p][alp];
        nowval = max(nowval, query(1, 1, idx, dfn[p]));
    }
    nowval += wordval[id];
    ans = max(ans, nowval);
    change(1, 1, idx, dfn[p], endfn[p], nowval);
}

void solve(int id){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%s", s+1);
        scanf("%d", &wordval[i]);
        insert();
        transfer_string(i);
    }
    
    buildacam();
    make_failtree();
    dfs(0, -1);
    idx ++;
    
    for(int i=1;i<=n;i++){
        solve_eachstring(i);
    }
    printf("Case #%d: %d\n", id, ans);
}
void duoceclear(){
    ans = 0;
    acamclear();
    graphclear();
    segtrclear();
}
int main(){
    int t;
    scanf("%d", &t);
    for(int i=1;i<=t;i++){
        solve(i);
        duoceclear();
    }
    return 0;
}