自动机学习笔记

chen_qian · 2021-06-22 20:23:03 · 个人记录

简单概念：

• 自动机：简单来说，一个自动机就是判定字符串是否满足一些要求。一般自动机是类似于一张图的结构，每个节点表示一个状态，状态与状态之间有转移边。边上标志通过当前边转移的条件。

• 分类：分为 ε-NFA, NFA 和 DFA，分别对应有ε转移的非确定有限自动机，非确定有限自动机，和确定有限自动机。所谓ε转移，即为没有条件的转移。而非确定则是指存在一个状态，其存在多个出边，限制条件相同，转移到的状态不同。比如说 a(c)* c ,建立一个满足这个限制的字符串（即开头为 a ,中间可以任意重复多次 c 。最后 c 结尾），那么建立出来的状态中有一个，存在两条 c 的转移边，一个指向自己，一个指向结束状态。

Trie 树

• trie 是最常见的自动机之一，它只接受给定的字符串集里的元素。

AC自动机

• AC自动机是基于 \text{kmp}+\text{trie} 的可以进行多串匹配的自动机，它只接受以指定的字符串集合中的某个元素为后缀的字符串。

• 相关概念：

  • 状态：AC自动机上一个节点对应一个状态，这个状态是从源点到这个节点上所有转移边组成的字符串，跟 \text{trie} 类似。

  • 失配(fail)指针：对于一个状态，其 \text{fail} 指针指向一个是其后缀且深度最深的状态。相当于就是 next 数组找最长前缀，只不过是在所有字符串中找。这个指针的作用是在当前走到的状态没有对应转移边，快速跳到有转移边的后缀。

• 构建:可以发现，AC自动机本身上就是比 \text{trie} 多了一个 \text{fail} 指针出来，我们考虑如何求出 fail 指针。考虑已经求出当前节点 x 的 \text{fail} 指针了。要求出 x 能转移到的新状态。

  • 枚举字符集，看有没有这条转移边。
  • 有，那么到达的新状态 y 只是往原状态 x 最后添加了一个字符。那么它的 \text{fail} 指针，应该指向 x 的 fail 指针指向的状态经过同样的转移边的状态。
  • 没有，那么当匹配到 x ，转移正巧是这个没有的转移，这个时候失配了，应该直接添加这条转移边，并指向 x 的 fail 指针指向状态通过对应转移能走到的边。
  • 源点设为 0 源点转移到的所有状态的 \text{fail} 指针都指向源点。

• 性质：

  • 假如仅看 \text{fail} 指针，可以得到一颗树形结构，且一个点 x 的子树就是所有以状态为后缀的节点。

序列自动机

• 序列自动机是只接受给定字符串的子序列的自动机。它基于贪心来构建。

• 构造方法：要判断一个字符串是否为给定字符串的子序列。一个贪心的方法匹配：对于当前匹配到的位置 x 。下一个字符是 a 。我们一定使用 x 后第一个为 a 的位置。基于这个贪心，序列自动机的每个转移边 k 都是指向他之后第一个为 k 的位置。

后缀自动机

• 后缀自动机是只接受给定字符串后缀的自动机。

• 相关概念：

  • 状态：与AC自动机相似的是，他也有着状态。根据 \text{endpos} 可以将所有子串划分成若干等价类。而一个状态就对应着同一个等价类的所有子串。那么根据定义，我们可以得到以下几个推论。

  • 对于同一个状态中的任意两个子串，u 和 v 。假设 |u|<|v|。那么 u 是 v 的后缀，且仅以 v 的后缀形式在 s 中出现。

  • 由上，我们推出一个结论。假如一个状态中最长的长度为 y，最短的为 x 。那么这个状态中的所有子串的长度完整覆盖 [x,y] 。

  • 后缀链接：由上的状态引出，既然一个状态的所有子串都是最长串的后缀。那么一个状态的后缀链接就应该指向是这个状态的最长串的的不属于这个 \text{endpos} 集合的最长后缀所在的状态，由此，我们要对于每个状态维护 len 。

• 构造：

  • 考虑将字符串中一个一个字符加入后缀自动机。并实时维护当前已加入的字符串的状态。

  • 假如加入字符 c。之前对应着整个字符串的状态为 last 。那么现在新建一个节点 k 。表示新的终止节点。这个新 \text{endpos}={x} 之前从未出现过（x 指当前的总长度）。可以直接将 len_k=len_{last}+1 。

  • 接下来添加转移边，顺便尝试定位它的后缀链接。从 last 往上跳后缀链接，假如没有 c 的转移，那么就添加转移到 k 。考虑这样做的正确性。往上跳找到 last 的都是后缀，加入 c 后相当于都多出来这些后缀后加上 c 的若干子串，而没有 c 转移，则说明从来没有出现过这些子串后加上 c 的情况。也就是说这些子串后加上 c 之后，得到的 \text{endpos} 相同，且就是 k 。知道找到一个有的状态 p 。

  • 现在对 p 进行考虑，假如没有 p 。那么 k 的后缀链接直接指向 -1。否则假设转移到的状态是 q 。那么如果 len_q=len_p+1 。这说明了这个状态的加上 c 后不作为任何状态的后缀出现。可以直接将 k 的后缀链接指向 q 。否则，就应该将 len_p+1 的状态分裂出来，新建节点 clone 。继承 q 除了 len 的所有信息，并将 len_{clone}=len_p+1 。同时 k 与 q 的后缀链接都指向 clone 。然后从 p 向上跳后缀链接，将所有指向 q 的转移指向 clone 。这一步很好理解。

• 性质

  • 考虑以上的实现过程，由于每次都是从前往后插入一个字符。那么新的状态 k 就该对应着当前整个字符串，也即 s 的一个前缀，我们将这些节点称为终止节点。那么对于一颗节点以对应的后缀链接为父亲的树，树上一个节点的 \text{endpos} 集合应该是其子树中所有终止节点所对应的终止位置。

广义后缀自动机

• 后缀自动机是接受单串的所有子串的自动机，那么广义后缀自动机就是接受若干串的子串的自动机。

• 考虑构造后缀自动机的过程，我们能够从前往后依次加入的原因是因为我们知道新加入的这个前缀一定没有在之前出现过，所以我们可以放心的新建一个 \text{endpos} 集合，但是在多串的时候，就不一定了，所以我们想一个办法，让相同的前缀同时被加入进去。所以我们想到了 \text{trie} ，先将所有的字符串构建到 \text{trie} 中，然后把 \text{trie} 中的每一个节点按照深度依次加入到自动机中，过程与普通后缀自动机构造无异。

void inserttrie(string t){
    int len=t.size(),x=0;
    for(int i=0;i<len;i++){
        int k=t[i]-'a';
        if(!ch[x][k]) ch[x][k]=++tot;
        x=ch[x][k];
    }
}
void buildtrie(){
    link[0]=-1;
    for(int i=1;i<=n;i++) inserttrie(s[i]);
}
int insert(int c,int last){
    int k=ch[last][c],p=link[last];
    //if(len[k]) return k;
    len[k]=len[last]+1;
    for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=k;
    if(p==-1) link[k]=0;
    else{
        int q=ch[p][c];
        if(len[q]==len[p]+1) link[k]=q;
        else{
            int nk=++tot;link[nk]=link[q],len[nk]=len[p]+1;
            for(int i=0;i<26;i++) if(len[ch[q][i]]) ch[nk][i]=ch[q][i];
            for(;p!=-1&&ch[p][c]==q;p=link[p]) ch[p][c]=nk;
            link[k]=link[q]=nk;
        }
    }
    return k;
}
void bfs(){
    queue<pii> q;
    for(int i=0;i<26;i++) if(ch[0][i]) q.push(mp(i,0));
    while(!q.empty()){
        pii x=q.front();q.pop();
        int last=insert(x.fi,x.se);
        for(int i=0;i<26;i++) if(ch[last][i]) q.push(mp(i,last));
    }
}