Early's Blog

Hello, World!

0%

序列自动机学习笔记

发表于 分类于
本文字数： 4.4k

简介

序列自动机是接受一个字符串的子序列的自动机。

它可以方便地维护 / 匹配字符串（数列）的所有子序列。

定义

设我们要维护的字符串为 SS，它的字符集大小为 sizsiz。

有两种构建序列自动机的方式：

  1. 构建所有子序列的复杂度为 O(∣S∣⋅siz)O(\mid S\mid\cdot siz)，查询所有子序列的复杂度即为所有子序列的个数；

  2. 构建复杂度 O(n)O(n)，查询一个子序列 TT 的复杂度为 O(∣T∣log⁡∣S∣)O(\mid T\mid\log\mid S\mid)。

两种实现方式的思想都是维护数组 nexi,cnex_{i,c}，表示 i+1i+1 至 nn 中第一次出现字符 cc 的位置。

第一种 - 实现

例题

建立

对于 X,YX,Y 序列，我们分别建一个序列自动机。

从后往前扫，每次将 nexinex_i 复制到 nexi−1nex_{i-1}，再把 nexi−1,Sinex_{i-1,S_i} 更新为 ii。

1
2
3
4
5
6
7
void build(int n,char s[],int nex[][SIZ]) {
    for (int i=n;i;--i) {
        memcpy(nex[i-1],nex[i],sizeof(nex[i]));
        nex[i-1][s[i]]=i;
    }
    return;
}

遍历

使用 dfs 并维护一个栈，访问节点时的栈即为该子序列。

依次访问每个字符指向的节点，访问时将字符加入栈，退出时再将栈顶弹出。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x)
{
    //Output/Use stk[]
    for(char i=0;i<SIZ;++i) {
        if(nex[x][i]) {
            stk[++top]=i;
            dfs(nex[x][i]);
            stk[top--]='\0';
        }
    }
    return;
}

代码

这例题竟然要高精度！😠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
const int N=3010,C=26,S=C<<1,D=20,M=1e9;
int m,n,k,a[N+1],b[N+1],nexa[N+1][S],nexb[N+1][S],top;
char x[N+2],y[N+2],res[N+2];
inline int max(int x,int y)
{
    return x>=y?x:y;
}
struct number {
    int dig;
    long long *s;
    bool vis;
    void init(long long val=0)
    {
        dig=0,vis=true;
        s=new long long[D];
        for(int i=0;i<D;++i) {
            s[i]=0;
        }
        if(val) {
            s[0]=val;
        }
        return;
    }
    void operator+=(const number ano)
    {
        dig=max(dig,ano.dig)+1;
        for(int i=0;i<=dig;++i) {
            s[i]+=ano.s[i];
            s[i+1]+=s[i]/M,s[i]%=M;
        }
        while(dig&&!s[dig]) {
            --dig;
        }
        return;
    }
};
number f[N+1][N+1];
void build(int n,int x[],int nex[][S])
{
    for(int i=n;i;--i) {
        memcpy(nex[i-1],nex[i],sizeof(nex[i]));
        nex[i-1][x[i]]=i;
    }
    return;
}
void dfs1(int x,int y)
{
    puts(res+1);
    for(int i=0;i<S;++i) {
        if(nexa[x][i]&&nexb[y][i]) {
            res[++top]=i<C?i+'A':i+'a'-26;
            dfs1(nexa[x][i],nexb[y][i]);
            res[top--]='\0';
        }
    }
    return;
}
void dfs2(int x,int y)
{
    if(f[x][y].vis) {
        return;
    }
    f[x][y].init(1);
    for(int i=0;i<S;++i) {
        if(nexa[x][i]&&nexb[y][i]) {
            dfs2(nexa[x][i],nexb[y][i]);
            f[x][y]+=f[nexa[x][i]][nexb[y][i]];
        }
    }
    return;
}
void print(number x)
{
    printf("%lld",x.s[x.dig]);
    for(int i=x.dig-1;~i;--i) {
        printf("%09lld",x.s[i]);
    }
    putchar('\n');
    return;
}
int main()
{
    scanf("%d%d",&m,&n);
    scanf("%s%s",x+1,y+1);
    scanf("%d",&k);
    for(int i=1;i<=m;++i) {
        a[i]=isupper(x[i])?x[i]-'A':x[i]-'a'+26;
    }
    for(int i=1;i<=n;++i) {
        b[i]=isupper(y[i])?y[i]-'A':y[i]-'a'+26;
    }
    build(m,a,nexa);
    build(n,b,nexb);
    if(k) {
        dfs1(0,0);
    }
    dfs2(0,0);
    print(f[0][0]);
    return 0;
}

第二种 - 实现

例题

建立

这种方式的建立十分简单。

用 vector 维护哪些位置上出现了某个字符。

1
2
3
4
5
6
7
void build(int n,char s[],vector<int>pos[])
{
    for(int i=1;i<=n;++i) {
        pos[s[i]].push_back(i);
    }
    return;
}

查询

假设当前查询到 TiT_i，且 Ti−1T_{i-1} 位于 SS 的第 laslas 位。

显然我们要在 TiT_i 的 vector 数组里找到一个 >las>las 的位置，选择它作为 TiT_i。

如果有多个点符合，那要选哪个点呢？

我们贪心选取最前面的一个点就可以了，因为：如果选后面的可以，改成选前面的显然也可以；如果选前面的不行，那么选后面的会跳过更多也许有用的结点。

二分一下，即可钦定找出最前的满足答案的点。

1
2
3
4
5
6
7
8
9
10
11
12
bool search(int len,char t[])
{
    for(int i=1;i<=l;++i) {
        auto p=upper_bound(pos[t[i]].begin(),pos[t[i]].end(),las);
        if(p==pos[t[i]].end()) {
            return false;
            break;
        }
        las=*p;
    }
    return true;
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5,M=1e5,L=1e6;
int n,q,m;
vector<int>pos[M+1];
int read()
{
    int ret=0;
    char c=getchar();
    while(!isdigit(c)) {
        c=getchar();
    }
    while(isdigit(c)) {
        ret=ret*10+c-'0';
        c=getchar();
    }
    return ret;
}
int main()
{
    read(),n=read(),q=read(),m=read();
    for(int i=1;i<=n;++i) {
        pos[read()].push_back(i);
    }
    while(q--) {
        bool res=true;
        int las=0;
        int l=read();
        static int val[L+1];
        for(int i=1;i<=l;++i) {
            val[i]=read();
        }
        for(int i=1;i<=l;++i) {
            auto p=upper_bound(pos[val[i]].begin(),pos[val[i]].end(),las);
            if(p==pos[val[i]].end()) {
                res=false;
                break;
            }
            las=*p;
        }
        puts(res?"Yes":"No");
    }
    return 0;
}

资料

序列自动机第二种部分参考浅谈子序列自动机 - WYXkk 的博客。