摘要: 序列自动机原理、代码模板、应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们串讲一下序列自动机的原理和代码模板。然后解决力扣 392。

序列自动机

在文章 词法分析-有限自动机 中，我们详细讲解了自动机的理论基础以及解决问题的过程。一个自动机的形式化定义为 $M = (S, \Sigma, f, S_{0}, F)$，其中 $S$ 是状态集、$\Sigma$ 是字母表、$f$ 是状态转移函数、$S_{0}$ 为初始状态、$F$ 为终结状态。

对于字符串来说，自动机可以理解为将字符串构造成一个有向无环图的过程。序列自动机就是其中一种构造过程，构造完成的序列自动机是一个接受且仅接受一个字符串的子序列的自动机，可以用于快速判断任意字符串 $t$ 是否包含子序列 $s$。序列自动机与 Trie 很像，只是 Trie 处理的是关于子串的问题。

子序列匹配有多种算法可以解决，参考文章 子序列匹配。如果固定 $t$，然后要查询很多次 $s$，判断 $s$ 是否是 $t$ 的子序列，就可以对 $t$ 建立序列自动机，之后的查询都在序列自动机上进行。

下面我们看一下由字符串 $t$ 构造的序列自动机 $M$ 的字母表、状态集合、转移函数、初始状态、终止状态。

• $t$ 中所有字符的集合构成了序列自动机的字母表 $\Sigma$。
• 若字符串 $t$ 包含 $n$ 个字符，那么序列自动机有 $n + 1$ 个状态，其中状态 1 到 n 分别代表 $t$ 的位置 0 到 n - 1，状态 0 代表初始状态。
• 状态转移函数 $j = f(i, ch)$ 表示从状态 i ($t$ 的 i - 1 位置) 读到下一个字符为 ch 时转移到状态 j ($t$ 的 j - 1 位置)，j 为 t[i..n-1] 上第一个出现 ch 字符的位置。
• 初始状态为节点 0。
• 所有状态都是终结状态，节点 0 表示空的子序列。

使用序列自动机解决子序列相关的问题，在实现的时候分为两步，第一步是根据 $t$ 建立自动机，第二步是查询。下面分别看。

建立序列自动机

前面我们描述的序列自动机的状态转移函数，可以通过二维数组 nxt 实现，定义如下：

nxt[i][ch] := t[i..n-1] 上第一个 ch 字符出现的位置
              如果 t[i..n-1] 没有 ch，则在 i 状态接收 ch 是不合法的，记为 -1 (初始化为 -1)

下面看一个例子 t = "abcbab"，n = 6，状态节点为 0 到 7，图中的边代表了状态转移函数，也就是 nxt：

从图中可以看出三个特性：

• 序列自动机相当于一棵树，树上每个节点到根的路径上的边代表的字符串就是所有不同的子序列。
• j = nxt[i][ch] 的意思是：节点 i 的第 ch 号出边连接到节点 j。
• 前 n 个状态（节点 0 到 n - 1）接受长度为 n - 1 的前缀的所有子序列；而第 i 个状态（节点 i - 1），接受长度为 i - 1 的前缀有、长度为 i - 2 的前缀没有的子序列。

在 $t$ 上建立 nxt 的过程比较简单，直接给出如下：

vector<vector<int>> build(const string& t)
{
    // 由字符串 t 建立序列自动机
    int n = t.size(); 
    int m = 26; // 字母表中的字符数
    vector<vector<int>> nxt(n + 1, vector<int>(m, -1)); // 状态节点 0 ~ n，字母表 0 ~ m-1
    
    for(int i = n - 1; i >= 0; --i)
    {
        for(int ch = 0; ch < 26; ++ch)
            nxt[i][ch - 'a'] = nxt[i + 1][ch - 'a'];
        nxt[i][t[i] - 'a'] = i + 1; 
    }
    return nxt;
}

查询子序列

定义指针 p = -1，每一轮 p 都跳转到 nxt[p + 1][j] 的位置，其中 j 为当前查询的字符。

bool find(const string& s)
{
    int l = s.size();
    int p = -1;
    for(int i = 0; i < l; ++i)
    {
        p = nxt[p + 1][s[i] - 'a'];
        if(p == -1)
            return false;
    }
    return true;
}

模板题：子序列匹配

• 392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false

算法：序列自动机

这是序列自动机的模板题，先对 t 建立序列自动机，然后查询 s 即可。

进阶问题中，先对 T 建立序列自动机，然后再对 S1, S2, …, Sk 查询。

子序列匹配还有贪心和动态规划算法，参考文章 子序列匹配。

代码 (C++，模板)

class SeqAM
{
public:
    SeqAM(){}
    SeqAM(const string& t)
    {
        build(t);
    }

    void build(const string& t)
    {
        // 由字符串 t 建立序列自动机
        int n = t.size(); 
        int m = 26; // 字母表中的字符数
        nxt.assign(n + 1, vector<int>(m, -1)); // 状态节点 0 ~ n，字母表 0 ~ m-1
        
        for(int i = n - 1; i >= 0; --i)
        {
            for(int ch = 0; ch < 26; ++ch)
                nxt[i][ch] = nxt[i + 1][ch];
            nxt[i][t[i] - 'a'] = i + 1; 
        }
    }

    bool find(const string& s) const
    {
        int l = s.size();
        int p = 0; // 初始状态
        for(int i = 0; i < l; ++i)
        {
            p = nxt[p][s[i] - 'a'];
            if(p == -1)
                return false;
        }
        return true;
    }

    int check_nxt(int i, int ch) const
    {
        return nxt[i][ch];
    }

private:
    vector<vector<int>> nxt;
};

class Solution {
public:
    bool isSubsequence(string s, string t) {
        SeqAM seq_am(t);
        return seq_am.find(s);
    }
};

---

题目

三个串不同的公共子序列种类数

• P1819 公共子序列

求 3 个字符序列有多少个不同的公共子序列，不包括空序列。

输入格式
第一行为一个正整数 n，表示 3 个序列的长度。
接下来 3 行，每行一个无空格长度为 n 的字符序列。只包含小写字母 a 到 z。

输出格式
一行一个正整数 ans，对 $10^{8}$ 取模。

数据范围
1 <= n <= 150

输入输出样例
输入
4
aabb
abab
baba
输出
5

算法：序列自动机 + 动态规划

首先对三个字符串 s1, s2, s3 分别建立序列自动机，然后在序列自动机上进行动态规划：

状态定义：
dp[x][y][z] := 从三个序列自动机上的 x, y, z 状态节点出发，可以得到的公共子序列种类数

序列自动机上的状态节点 x, y, z，对应 s1, s2, s3 三个字符串的 x - 1，y - 1，z - 1 位置。

三个序列自动机同时从节点 0 出发，走的步数是阶段，在三个序列自动机上的位置 x, y, z 是附加状态。

每一个阶段要做的决策是确定一个属于公共子序列的字符，各阶段的决策序列对应一个公共子序列，

比如说当前已经进行了 i 个阶段，在三个序列自动机上的位置分别为 x, y, z，前 i 个阶段的决策序列确定了公共子序列的前 i 个字符。

下面进行第 i + 1 个阶段的决策，进而计算出 dp[x][y][z]，也就是从三个序列自动机的 (x, y, z) 节点组出发可以取到的公共子序列个数。

考察 s1[x..n-1], s2[y..n-1], s3[z..n-1]：

• 如果没有公共的字符，则从三个自动机的 (x, y, z) 节点组出发，取不到任何子序列。于是 dp[x][y][z] = 0。
• 如果有公共的字符 ch，于是状态可以转移到 nxt_x, nxt_y, nxt_z：

nxt_x = seq_am1.nxt[x][ch]
nxt_y = seq_am2.nxt[y][ch]
nxt_z = seq_am3.nxt[z][ch]

由于 ch 本身是一个长度为 1 的公共子序列，于是 dp[x][y][z] += 1，至于有没有更多，那就要看下一个阶段求出的 dp[nxt_x][nxt_y][nxt_z] 了。于是状态转移方程如下：

dp[x][y][z] += 1 + dp[nxt_x][nxt_y][nxt_z]

答案就是 dp[0][0][0]。

完整的在三个序列自动机上的动态规划算法如下：

状态定义：
dp[x][y][z] := 从三个序列自动机上的 x, y, z 状态节点出发，可以得到的公共子序列种类数

答案：
dp[0][0][0]

状态转移：
dp[x][y][z] += 1 + dp[nxt_x][nxt_y][nxt_z]
其中 (x, y, z) 经过 ch 对应的边到达 (nxt_x, nxt_y, nxt_z)

代码 (C++)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

using ll = long long;
const int MOD = 1e8;

class SeqAM
{
public:
    SeqAM(){}
    SeqAM(const string& t)
    {
        build(t);
    }

    void build(const string& t)
    {
        // 由字符串 t 建立序列自动机
        int n = t.size();
        int m = 26; // 字母表中的字符数
        nxt.assign(n + 1, vector<int>(m, -1)); // 状态节点 0 ~ n，字母表 0 ~ m-1

        for(int i = n - 1; i >= 0; --i)
        {
            for(int ch = 0; ch < 26; ++ch)
                nxt[i][ch] = nxt[i + 1][ch];
            nxt[i][t[i] - 'a'] = i + 1;
        }
    }

    bool find(const string& s) const
    {
        int l = s.size();
        int p = 0; // 初始状态
        for(int i = 0; i < l; ++i)
        {
            p = nxt[p][s[i] - 'a'];
            if(p == -1)
                return false;
        }
        return true;
    }

    int check_nxt(int i, int ch) const
    {
        return nxt[i][ch];
    }

private:
    vector<vector<int> > nxt;
};

vector<vector<vector<int> > > dp;
SeqAM seq_am1;
SeqAM seq_am2;
SeqAM seq_am3;
int n;

int dfs(int x, int y, int z)
{
    // 动态规划
    if(dp[x][y][z] != -1)
        return dp[x][y][z];

    dp[x][y][z] = 0;
    for(int i = 0; i < 26; ++i)
    {
        int nxt_x = seq_am1.check_nxt(x, i);
        int nxt_y = seq_am2.check_nxt(y, i);
        int nxt_z = seq_am3.check_nxt(z, i);
        if(nxt_x != -1 && nxt_y != -1 && nxt_z != -1)
        {
            // i 字符同时在三个后缀串中
            dp[x][y][z] = ((ll)dp[x][y][z] + 1 + dfs(nxt_x, nxt_y, nxt_z)) % MOD;
        }
    }
    return dp[x][y][z];
}

int main()
{
    cin >> n;
    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;
    seq_am1.build(s1);
    seq_am2.build(s2);
    seq_am3.build(s3);
    dp.assign(n + 1, vector<vector<int> >(n + 1, vector<int>(n + 1, -1)));
    cout << dfs(0, 0, 0) << endl;
}

一个串不同子序列个数

• 940. 不同的子序列 II

本题相关内容参考文章 力扣940-不同的子序列。

回文子序列个数

• 730. 统计不同回文子字符串

本题相关内容参考文章 力扣730-统计不同回文子序列。

---