浅谈序列自动机

发布于 2021-06-23  170 次阅读


最高端的食材往往只需要最简单的烹饪。 ——序列自动机

另外,食用前提示:本文默认所有字符串的下标从 $1$ 开始。

啧,进入正题吧。

原理&构造

序列自动机,听上去高端大气上档次,实则只是一个大小为 字符串长度 $\times$ 字符集大小的数组。

我们用数组 $nxt_{i,j}$ 表示在字符串中,位置 $i$ 以后第一次出现字符 $j$ 的位置。

那么,在构造序列自动机的时候,我们从最后一位开始倒着构造,每次进行如下操作:

  • 把后一个位置的的 $nxt$ 全部继承过来。
  • 处理后一个位置的字符的影响,即,修改 $nxt[当前位置][后一个位置的字符]$ 即可。

构建的时间和空间复杂度都为 $O(len \times |C|)$ ,其中 $len$ 为字符串长度,$|C|$ 为字符集大小。

代码如下,细节看注释:

inline void Build_Automaton(){
    for (int i=lenS-1;i>=0;--i){
        // 注意这里 i 从 lenS-1 到 0 ,第 lenS 位后不存在字符不需要处理
        for (int j=0;j<=25;++j)
            nxt[i][j]=nxt[i+1][j];
        nxt[i][s[i+1]-'a']=i+1;     // 处理后一个位置的影响
    }
}
//这里如果 nxt[i][j]==0 则表示在第 i 个位置后没有出现过字符 j 

这东西的原理是什么呢?

我们可以把序列自动机理解成一个 $DAG$,或者,形象化地,一张地图。

在字符串的每一位,对于任何一个字符,我们都储存了下一个该去的地方是哪里(所以说序列自动机真的很暴力啊),以此达到匹配的效果。

那么有了这么一个东西,我们用它来干什么呢?

跳!

题一

[计蒜客 38232] SubSequence

给定一个字符串 $S$ ,再给定 $n$ 个字符串 $T_i$ ,要求对于所有 $T_i$ ,判断 $T_i$ 是不是 $S$ 的子串。

$n,|S| \le 10^5$,$|T_i| \le 10^3$。

当当当当,这就是序列自动机最朴实(简单)的一个应用,在单次 $O(n)$ 的复杂度内来判断一个串是不是另一个串的子串

我们可以把 $S$ 的序列自动机建出来。

我们用一个变量 $now$ 表示当前匹配到了 $S$ 的哪一位,初始值为 $0$,然后从 $T$ 的第一位开始,每次把 $now$ 根据当前这位 $T$ 要匹配的字符跳到后面第一次出现这个字符的位置,最后如果匹配完了 $T$ 的所有位置,$now$ 还在串 $S$ 中,就说明 $T$ 是 $S$ 的子串,如果中途发现 $now=0$(即后面不存在需要被匹配的字符),则说明失配了。

为什么这样做是正确的呢?

这是一个简单的贪心思想。我们考虑如上图的例子,假设我们要匹配的串是 $\texttt{abc}$,那么我们在 $a$ 的位置往后,发现跳到第一个 $b$ 的位置一定是比跳到第二个 $b$ 的位置更优,因为这样可以给后面的串留下更多的空间(比如说,当 $c$ 出现在红色的位置时,如果跳第二个 $b$ 就无法匹配了)。

部分代码:

int now=0; bool flag=true;
for (int i=1;i<=lenT;i++){
    now=nxt[now][t[i]-'a'];
    if (now==0){
        flag=false;
        break;
    }
}

完整代码(水字数)

#include<bits/stdc++.h>
using namespace std;
const int N=100005;

int T,lenS,lenT,nxt[N][26];
char s[N],t[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void Build_Automaton(){
    for (int i=lenS-1;i>=0;--i){
        for (int j=0;j<=25;++j)
            nxt[i][j]=nxt[i+1][j];
        nxt[i][s[i+1]-'a']=i+1;
    }
}

int main(){
    //freopen("Sequential Automaton.in","r",stdin);
    //freopen("Sequential Automaton.out","w",stdout);
    scanf("%s",s+1);
    lenS=strlen(s+1);
    Build_Automaton();
    T=read();
    while (T--){
        scanf("%s",t+1); 
        lenT=strlen(t+1);
        int now=0; bool flag=true;
        for (int i=1;i<=lenT;i++){
            now=nxt[now][t[i]-'a'];
            if (now==0){
                flag=false;
                break;
            }
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

题二

[Luogu 5826] 子序列自动机

给定一个长度为 $n$ 的正整数序列 $a$,有 $q$ 次询问,第 $i$ 次询问给定一个长度为 $L_i$ 的序列 $b_i$,请你判断 $b_i$ 是不是 $a$ 的子序列。序列 $a$ 和所有 $b_i$ 中的元素都不大于一个给定的正整数 $m$。

$n,m,q \le 10^5$,$L_i \le 10^6$,$\sum L_i \le 10^6$。

小剧场:

你:诶这是不是和上面那道题一模一样啊?(狂喜)

你迫不及待地敲了一个序列自动机。

你提交了代码,并觉得自己又水过了一道蓝题。

你获得了 $55~pts$ 的高分。

咳咳,好的,我们还是回归正题。

注意这道题里是序列而不是字符串,每一个元素的最大值是 $10^5$ 级别的。

于是在这题中需要 $O(nm)$ 构建的序列自动机在时间上和空间上就都不行了。

诶,怎么办呢?

我们注意到一个有意思的性质:在序列自动机的构建过程中,前面一个位置相比于后面一个位置只改变了 $1$ 个位置的值!

算法 $1$ :

我会可持久化平衡树!我们可以从后向前使用可持久化线段树来维护每个位置的跳跃数组,然后每次查询后面的最近的点,这样建立自动机的时间复杂度为 $O(n \log m)$,匹配的时间复杂度为 $O(\sum L \log m)$。总时间复杂度 $O((n + \sum L) \log m)$。

不过我不会写!

伪代码(From Here):

[主席树板子]
int main(){
    输入S
    root[len(S)]=空树(字符集)
    for(i=len(S)->1){
        root[i-1]=root[i];
        修改a[S[i-1]]=i-1;
    }
    输入q
    for(i=1->q){
        flg=true,pos=0
        输入T
        for(j=1->len(T))
        {
            t=query(root[pos],T[j])
            if(t==-1) flg=false,break
            else pos=t
        }
        puts(flg?"Yes":"No")
    }
}
算法 $2$:

我只要用二分就可以了!

我们开 $m$ 个 std::vector 存储每个值对应的下标,每次跳的时候用二分找当前值在后面出现的第一个位置即可(然而不是序列自动机的解法)。时间复杂度为 $O(n+(\sum L) \log m)$。

这里给出算法 $2$ 的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100005;

int type,n,Q,m,a[N];
vector <int> vec[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main(){
    //freopen("Luogu5826.in","r",stdin);
    //freopen("Luogu5826.out","w",stdout);
    type=read(),n=read(),Q=read(),m=read();
    for (int i=1;i<=n;++i){
        a[i]=read();
        vec[a[i]].push_back(i);
    }
    while (Q--){
        int len=read(),now=0;
        bool flag=true;
        for (int i=1;i<=len;++i){
            int x=read(); if (!flag) continue;
            vector <int> :: iterator it=lower_bound(vec[x].begin(),vec[x].end(),now+1);
            if (it==vec[x].end()) flag=false;
            else now=(*it);
        }
        printf(flag ? ("Yes\n") : ("No\n"));
    }
    return 0;
}

题三

[FJOI2016] 所有公共子序列问题

要求对于给定的两个字符串 $S$ 和 $T$ ,找出 $S$ 和 $T$ 的所有不同的公共子序列。

输入的最后给出整数 $k$,$k$ 的值为 $1$ 时,表示计算结果要按字典序输出 $S$ 和 $T$ 的所有不同的公共子序列,以及 $S$ 和 $T$ 有多少个不同的公共子序列。

$k$ 的值为 $0$ 时,表示计算结果只要输出 $S$ 和 $T$ 有多少个不同的公共子序列。

$|S|,|T| \le 3010$,$k \in [0,1]$。

我们先把两个序列自动机建出来,分别设为 $nxt1$ 和 $nxt2$。

令 $f_{i,j}$ 表示从 $S$ 中的第 $i$ 个字符开始,$T$ 串中第 $j$ 个字符开始的公共子序列个数。

那么显然有 $f[i][j]=\sum f[nxt1[i][k]][nxt2[j][k]]$(可以理解为在 $DAG$ 上 $Dp$)。

而对于按字典序输出,我们只要优先走字典序靠前的字母,每次用一个栈一样的字符串记录字符串即可。

理论时间复杂度为 $O(|S|\cdot|T|\cdot 26)$ ,但实际上远远跑不到这个上界。

自信开一手 $long~long$ ,然后交上去你会发现诶?答案怎么出现负数了?

顿时感觉被恶心到了,写一个高精,交上去。诶?怎么 $MLE$ 了?

所以,这道题其实要写压位高精。。。(充满了$FJOI$ 特色)

写了我一个上午,写到自闭。

由此可见解决序列自动机的一种套路就是利用 $dfs$ 同时在目标串上跳,边跳边统计答案。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9;
const int N=3020,L=58,K=25;

int la,lb,k;
char a[N],b[N];
char sta[N];
int top=-1;
int nxt1[N][L],nxt2[N][L];
ll ans;

struct BigNum{
    int cur;
    ll *s;

    inline void init(){
        s=new long long[20];
        for(int i=0;i<20;i++) s[i]=0;
        cur=0;
    }

    inline void put(){
        printf("%lld",s[cur]);
        for(int i=cur-1;i>=0;i--) printf("%09lld",s[i]);
    }

    inline void add(ll k){
        s[0]+=k;
        int i=0;
        while(s[i]>=mod) s[i+1]+=s[i]/mod,s[i++]%=mod;
        while(s[cur+1]) cur++;
    }

    inline void Add(const BigNumNum& o){
        ll i,r=max(cur,o.cur);
        for(int i=0;i<=r;i++){
            s[i]+=o.s[i];
            if(s[i]>=mod) s[i+1]+=s[i]/mod,s[i]%=mod;
        }
        cur=min(r+3,19ll);while(cur&&s[cur]==0) cur--;
    }
}dp[N][N];

bool vis[N][N];

inline void build1(){
    memset(nxt1[la],-1,sizeof nxt1[la]);
    for(int i=la;i;i--){
        memcpy(nxt1[i-1],nxt1[i],sizeof nxt1[i]);
        nxt1[i-1][a[i]-'A']=i;
    }
}

inline void build2(){
    memset(nxt2[lb],-1,sizeof nxt2[lb]);
    for(int i=lb;i;i--){
        memcpy(nxt2[i-1],nxt2[i],sizeof nxt2[i]);
        nxt2[i-1][b[i]-'A']=i;
    }
}

inline void dfs2(int x,int y){
    if(vis[x][y]) return;
    vis[x][y]=1;
    dp[x][y].init();
    dp[x][y].add(1);
    for(int i=0;i<=57;i++){
        if(nxt1[x][i]!=-1 && nxt2[y][i]!=-1){
        dfs2(nxt1[x][i],nxt2[y][i]);
        dp[x][y].Add(dp[nxt1[x][i]][nxt2[y][i]]);
        }
    }
}

inline ll dfs1(int x,int y){
    printf("%s\n",sta);
    ll cnt=1;
    for(int i=0;i<=57;i++){
        if(nxt1[x][i]!=-1 && nxt2[y][i]!=-1){
        sta[++top]=i+'A';
        cnt+=dfs1(nxt1[x][i],nxt2[y][i]);
        sta[top--]=' ';
        }
    }
    return cnt;
}

int main(){
    //freopen("Luogu4608.in","r",stdin);
    //freopen("Luogu4608.out","w",stdout);
    scanf("%d%d",&la,&lb);
    scanf("%s",a+1);scanf("%s",b+1);    
    scanf("%d",&k);
    build1(); build2();
    if(k==1) dfs1(0,0);
    dfs2(0,0);
    dp[0][0].put();
    return 0;
}

总结

序列自动机是处理子序列问题的有力工具,但是现在考的概率不大,除了一些经典应用之外也许可以用于写一些乱搞,而且序列自动机代码量小,学不了吃亏,学不了上当。

就这样吧。


我们无法选择过去,但我们可以改变未来。