字符串#

子串可以看成前缀的一个后缀

前缀函数#

$\pi[i]$ 是 $s[0...i]$ 最长的相等的真前缀与真后缀的长度。 $\pi[i]=\max_{k=0...i}k,s[0...k-1]=s[i-k+1...i]$ 特别的规定 $\pi[0]=0$ 假设我们已经知道前 $i$ 个 $\pi$ 函数值，考虑计算 $\pi[i+1]$ ,如果 $s[i+1]=s[\pi[i]+1]$ ,那么， $\pi[i+1]=\pi[i]+1$ ,如果不相等，我们考虑找到一个第二长的相等的真前缀与真后缀的长度，发现 $s[0...\pi[i]]和s[i-\pi[i]+1...i]$ 完全相等，那么我们要找的第二长是不是就是 $s[0...\pi[i]]$ 的最长，所以，我们这样一步一步跳即可。

1
void pre(string s){
2
    int len=s.length();
3
    pi[0]=0;
4
    for (int i=1;i<len;i++){
5
        int j=pi[i-1];
6
        while(j&&s[i]!=s[j])j=pi[j-1];
7
        pi[i]=j+(s[i]==s[j]);
8
    }
9
}

KMP#

给定一个文本 𝑡和一个字符串 𝑠，我们尝试找到并展示 𝑠 在 𝑡 中的所有出现我们发现，只要处理 $s+$ # $+t$ 就可以 #代指不在 $s,t$ 的任意一个字符代码同上

AC自动机#

Trie 上的自动机建立需要两个步骤 1.基础的 Trie 结构：将所有的模式串构成一棵 Trie； 2.KMP 的思想：对 Trie 树上所有的结点构造失配指针。 字典树正常建树就可以，我们来看一下失配指针 fail指针指向所有模式串的前缀中匹配当前状态的最长后缀，上文的 $\pi$ 指向本模式串，接下来我们考虑怎么计算fail函数 仔细想一下，发现其实和 $\pi$ 函数求法是一样的。考虑字典树中当前的结点 𝑢，𝑢的父结点是 𝑝，𝑝通过字符 𝑐的边指向 𝑢，即 $trie⁡(𝑝,𝑐) =𝑢$ 。假设深度小于 𝑢 的所有结点的 $fail$ 指针都已求得。 1.如果 $trie⁡(fail⁡(𝑝),𝑐)$ 存在：则让 𝑢的 fail 指针指向 $trie⁡(fail⁡(𝑝),𝑐)$ 。相当于在 $𝑝$ 和 $fail⁡(𝑝)$ 后面加一个字符 𝑐，分别对应 𝑢 和 $fail⁡(𝑢)$ ； 2.如果 $trie⁡(fail⁡(𝑝),𝑐)$ 不存在：那么我们继续找到 $trie⁡(fail⁡(fail⁡(𝑝)),𝑐)$ 。重复判断过程，一直跳 $fail$ 指针直到根结点； 3.如果依然不存在，就让 $fail$ 指针指向根结点。

建树过程#

比较抽象，什么时候我想到一个说法我再详细说我们考虑优化一下第二步的跳跃，发现这是在跳 $fail$ 指针，如果我们将 $fail$ 指针的结构加到树上会怎么样呢？

1
void build(){
2
    //建立ac自动机
3
    while (!Q.empty()) Q.pop();
4
    for (int i=0;i<26;i++)
5
        if (T[0].son[i])Q.push(T[0].son[i]);
6
    while (!Q.empty()){
7
        int u=Q.front();Q.pop();
8
        for (int i=0;i<26;i++){
9
            if (T[u].son[i]){
10
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
11
                Q.push(T[u].son[i]);
12
            }
13
            else T[u].son[i]=T[T[u].fail].son[i];//改变树的结构
14
        }
15
    }
16
}

简单画个图，我们发现改变树的结构帮我们一次跳到了所需位置（后期再补）

查询操作及其优化#

首先，我们先考虑ACAM上每个节点是什么意思。每个节点可以看做是一个字符串的前缀（从根节点到当前节点所经过的边形成的前缀）。我们称其为该点的状态。那我们的 $fail$ 指针又是干什么的的呢？我们发现， $fail$ 指针指向当前穿的最长的后缀。那么，我们每次查寻到一个点，首先，能达到该点的状态，然后其 $fail$ 所指的状态也能达到，每次到一个点，我们就跳 $fail$ 来统计答案。发现每次都要跳，很浪费，我们又只需要在 $fail$ 上跳（显然 $fail$ 所形成的是DAG），所以我们考虑用拓扑排序优化。

1
void qry(string t){
2
    int u=0,len=t.length();
3
    for (int i=0;i<len;i++){
4
        u=T[u].son[t[i]-'a'];
5
        T[u].ans++;
6
    }
7
}
8
void topo(){
9
    while (!Q.empty()) Q.pop();
10
    for (int i=0;i<=cntn;i++){
11
        if (!T[i].in)Q.push(i);
12
    }
13
    while (!Q.empty()){
14
        int u=Q.front();Q.pop();
15
        ans[T[u].id]=T[u].ans;
16
        int v=T[u].fail;
17
        T[v].ans+=T[u].ans;
18
        if (!--T[v].in)Q.push(v);
19
    }
20
}

AC自动机模板 ACAM完整代码

1
namespace ACAM {
2
    struct tire{
3
        int son[26],fail,in,id,ans;
4
        void clear(){
5
            fail=in=id=ans=0;
6
            memset(son,0,sizeof(son));
7
        }
8
    }T[N];
9
    int cntid,cntn,ans[N];
10
    queue<int>Q;
11
    void init(){
12
        cntid=cntn=0;
13
        T[0].clear();
14
    }
15
    int insert(string s){//return id;
16
        int u=0,len=s.length();
17
        for (int i=0;i<len;i++){
18
            int& son=T[u].son[s[i]-'a'];//地址写法更方便
19
            if (!son)son=++cntn,T[son].clear();
20
            u=son;
21
        }
22
        if (!T[u].id)T[u].id=++cntid;//防止重复
23
        return T[u].id;//记录编号
24
    }
25
    void build(){
26
        //建立ac自动机
27
        while (!Q.empty()) Q.pop();
28
        for (int i=0;i<26;i++)
29
            if (T[0].son[i])Q.push(T[0].son[i]);
30
        while (!Q.empty()){
31
            int u=Q.front();Q.pop();
32
            for (int i=0;i<26;i++){
33
                if (T[u].son[i]){
34
                    T[T[u].son[i]].fail=T[T[u].fail].son[i];
35
                    T[T[T[u].fail].son[i]].in++;
36
                    Q.push(T[u].son[i]);
37
                }
38
                else T[u].son[i]=T[T[u].fail].son[i];//改变树的结构
39
            }
40
        }
41
    }
42
    void qry(string t){
43
        int u=0,len=t.length();
44
        for (int i=0;i<len;i++){
45
            u=T[u].son[t[i]-'a'];
46
            T[u].ans++;
47
        }
48
    }
49
    void topo(){
50
        while (!Q.empty()) Q.pop();
51
        for (int i=0;i<=cntn;i++){
52
            if (!T[i].in)Q.push(i);
53
        }
54
        while (!Q.empty()){
55
            int u=Q.front();Q.pop();
56
            ans[T[u].id]=T[u].ans;
57
            int v=T[u].fail;
58
            T[v].ans+=T[u].ans;
59
            if (!--T[v].in)Q.push(v);
60
        }
61
    }
62
}

ACAM上的DP#

String

https://fuwari.vercel.app/posts/string/

Author

Ender子浪

Published at

2025-11-28

License

CC BY-NC-SA 4.0

Mysterious_Technology

test01