序列自动机

What · 是什么

序列自动机（sequence automaton）是接受且仅接受给定串 s 的全部子序列的 DFA：状态 0..n（n=|s|），状态 i 表示'已匹配到 s 的前 i 个字符'，转移 δ(i,c)=s 中 i 之后（严格大于 i）字符 c 第一次出现的位置，即 next[i][c]=min{j | j>i, s[j]=c}（不存在为 null）。所有状态都是接受状态。构造：从后向前扫描，维护每个字符当前最近出现位置 last[c]，则 next[i][c]=last[c]，之后 last[s[i]]=i。复杂度 O(n|Σ|)。应用：判断 t 是否为 s 的子序列（贪心沿 next 走，O(|t|)）；计数 s 的不同子序列数；与其他自动机叠加做 DP（如 HEOI2015 最短不公共子序列）；字典序第 k 小子序列等。

Why · 为什么

How · 实现

伪代码

# 构造 O(n|Σ|)
last[c] = null (所有 c)
next = [n+1][|Σ|] 全 null
for i = n-1 downto 0:
    for c in Σ: next[i][c] = last[c]
    last[s[i]] = i
# 判断 t 是否子序列
pos = 0
for ch in t:
    pos = next[pos][ch]
    if pos == null: return False
    pos += 1    # 匹配后移到 pos+1
return True

Python 实现

# -*- coding: utf-8 -*-
# 序列自动机：状态 i 表示已匹配 s[0..i-1]（消耗了前 i 个字符）。
# next[i][c] = s 中位置 >= i 的字符 c 第一次出现的位置；不存在为 -1。
# 匹配时：u = next[u][ch]；若为 -1 失败；否则 u += 1（消耗该字符）。
def build_seq(s, sigma=26):
    """返回 next: (n+1) x sigma 数组。"""
    n = len(s)
    nxt = [[-1] * sigma for _ in range(n + 1)]
    last = [-1] * sigma                 # 扫描过的后缀中 c 的最前出现位置
    for i in range(n, 0, -1):           # 状态 i 的转移来自位置 >= i 的后缀
        nxt[i] = last[:]
        last[ord(s[i - 1]) - 97] = i - 1
    nxt[0] = last[:]                    # 状态 0 可用整个串（位置 >= 0）
    return nxt


def is_subsequence(nxt, t, sigma=26):
    """判断 t 是否为 s 的子序列。"""
    u = 0
    for ch in t:
        u = nxt[u][ord(ch) - 97]
        if u == -1:
            return False
        u += 1                          # 消耗该字符，下次查找从 u 开始
    return True


def count_distinct_subseq(s, sigma=26):
    """s 的不同子序列数（含空串）。经典去重 DP：g(u)=2*g(u+1)-g(同字符下次出现位置+1)。"""
    n = len(s)
    g = [0] * (n + 1)
    g[n] = 1
    nxtp = [-1] * sigma                 # 当前位置右边同字符首次出现
    for i in range(n - 1, -1, -1):
        c = ord(s[i]) - 97
        g[i] = 2 * g[i + 1]
        p = nxtp[c]                     # s[i] 在 i 之后第一次出现的位置
        if p != -1:
            g[i] -= g[p + 1]
        nxtp[c] = i
    return g[0]


if __name__ == '__main__':
    s = 'abcde'
    nxt = build_seq(s)
    for t in ['ace', 'aec', 'b', 'ad', '', 'zz', 'de']:
        def brute(t):
            i = 0
            for ch in s:
                if i < len(t) and ch == t[i]:
                    i += 1
            return i == len(t)
        assert is_subsequence(nxt, t) == brute(t), (t, is_subsequence(nxt, t), brute(t))
    import random
    random.seed(0)
    for _ in range(200):
        n = random.randint(1, 10)
        s2 = ''.join(random.choice('abc') for _ in range(n))
        nx = build_seq(s2)
        for _ in range(10):
            m = random.randint(0, 6)
            t = ''.join(random.choice('abc') for _ in range(m))
            def brute2(t):
                i = 0
                for ch in s2:
                    if i < len(t) and ch == t[i]:
                        i += 1
                return i == len(t)
            assert is_subsequence(nx, t) == brute2(t), (s2, t)
    # 不同子序列数暴力验证
    for s3 in ['ab', 'aaa', 'abc', 'aba', 'abcabc', 'banana']:
        n3 = len(s3)
        alls = set([''])
        for i in range(n3):
            for j in range(i + 1, n3 + 1):
                for mask in range(1 << (j - i)):
                    sub = ''.join(s3[i + k] for k in range(j - i) if (mask >> k) & 1)
                    alls.add(sub)
        assert count_distinct_subseq(s3) == len(alls), (s3, count_distinct_subseq(s3), len(alls))
    print('seq-automaton tests passed')

易错点

• next[i][c] 记的是'第一次出现位置'，判断子序列时要 pos+=1 跳过已用字符
• 状态从 0（未匹配）到 n（匹配完整个 s），n+1 个状态；next[n] 全为 -1
• 构造是倒序扫描，last 数组维护后缀最前出现，顺序错了会错位
• 不同子序列计数去重公式易错：dp[i]=1+Σ(dp[nxt+1]−1)，不要漏减重复空串
• 字符集下界注意：'a'..'z' 的偏移或离散化

例题

信源

• OI Wiki✓ https://oi-wiki.org/string/seq-automaton/
• 书籍✓ HEOI2015 最短不公共子串（loj 2123）题解