后缀自动机(SAM)

What · 是什么

后缀自动机（Suffix Automaton, SAM）是识别给定字符串 s 所有后缀的最小 DFA，等价地包含 s 全部子串的压缩信息：从初始状态 t0 出发的任意路径的标号都是 s 的一个子串，反之每个子串对应一条路径。状态是子串按 endpos 集合（出现结束位置集合）划分的等价类，后缀链接 link(v) 指向 endpos 更大的最长后缀等价类，形成后缀链接树（=endpos 集合的包含树）。性质：状态数 ≤2n−1，转移数 ≤3n−4，构造 O(n)（字符集常数量级；字符集大时 O(n log|Σ|)）。在线增量构造：每加一个字符创建 cur（len[last]+1），沿后缀链接补充转移；遇到已有转移 p→c 时，若 len[p]+1==len[q] 直接连 link，否则复制 clone。应用：不同子串数=Σ(len[v]−len[link[v]])；子串出现次数=沿 link 树从前缀状态向上累计；最小循环移位；两串最长公共子串；字典序第 k 小子串；第一次/所有出现位置。

Why · 为什么

How · 实现

伪代码

# 增量构造
t0: len=0, link=-1; last=t0
sam_extend(c):
    cur = 新状态(len[last]+1)
    p = last
    while p!=-1 and p 无 c 转移:
        p 加 c->cur; p = link[p]
    if p==-1:
        link[cur] = 0
    else:
        q = p 的 c 转移
        if len[p]+1 == len[q]: link[cur]=q
        else:
            clone = 复制 q(len=len[p]+1, 转移, link)
            while p!=-1 and p 的 c 转移 == q:
                p 的 c 转移 = clone; p = link[p]
            link[q] = link[cur] = clone
    last = cur

# 不同子串数 = sum(len[v]-len[link[v]])
# 出现次数: 前缀状态 sz=1, 按 len 降序沿 link 累加

Python 实现

# -*- coding: utf-8 -*-
# 后缀自动机完整实现（O(n)），含常见应用

class SAM:
    """用 dict 存转移；字符集为常数时可换数组。"""
    def __init__(self):
        self.next = []      # 转移
        self.link = []      # 后缀链接
        self.len = []       # 状态最长串长度
        self.last = 0
        self._new(0, -1)

    def _new(self, l, lk):
        self.next.append({})
        self.link.append(lk)
        self.len.append(l)
        return len(self.len) - 1

    def extend(self, c):
        cur = self._new(self.len[self.last] + 1, -1)
        p = self.last
        while p != -1 and c not in self.next[p]:
            self.next[p][c] = cur
            p = self.link[p]
        if p == -1:
            self.link[cur] = 0
        else:
            q = self.next[p][c]
            if self.len[p] + 1 == self.len[q]:
                self.link[cur] = q
            else:
                clone = self._new(self.len[p] + 1, self.link[q])
                self.next[clone] = self.next[q].copy()
                while p != -1 and self.next[p].get(c) == q:
                    self.next[p][c] = clone
                    p = self.link[p]
                self.link[q] = self.link[cur] = clone
        self.last = cur


def build_sam(s):
    sam = SAM()
    for ch in s:
        sam.extend(ch)
    return sam


def count_distinct_substrings(s):
    """不同子串数 = Σ(len[v]-len[link[v]])。"""
    sam = build_sam(s)
    return sum(sam.len[i] - sam.len[sam.link[i]] for i in range(1, len(sam.len)))


def max_occurrence(s):
    """s 中任意子串的最大出现次数。"""
    sam = build_sam(s)
    n = len(sam.len)
    sz = [0] * n
    last = 0
    for ch in s:                       # 前缀状态各计 1
        last = sam.next[last][ch]
        sz[last] += 1
    order = sorted(range(1, n), key=lambda i: sam.len[i], reverse=True)
    for v in order:                    # 沿 link 树向上累计
        if sam.link[v] >= 0:
            sz[sam.link[v]] += sz[v]
    return max(sz[1:])                 # 排除根（根非子串）


def longest_common_substring(a, b):
    """两串最长公共子串长度（SAM on a，扫描 b）。"""
    sam = build_sam(a)
    v, l, best = 0, 0, 0
    for ch in b:
        while v != -1 and ch not in sam.next[v]:
            v = sam.link[v]
            if v != -1:
                l = sam.len[v]
        if v == -1:
            v, l = 0, 0
        else:
            v = sam.next[v][ch]
            l += 1
            best = max(best, l)
    return best


if __name__ == '__main__':
    assert count_distinct_substrings('abc') == 6
    assert count_distinct_substrings('aaaa') == 4
    assert count_distinct_substrings('ababa') == 9
    assert max_occurrence('ababa') == 3        # 'a' 出现 3 次
    assert max_occurrence('aaaa') == 4
    assert longest_common_substring('abcde', 'cdefg') == 3   # 'cde'
    assert longest_common_substring('abcdef', 'xyz') == 0
    assert longest_common_substring('abcabc', 'bca') == 3    # 'bca'
    # 随机对拍
    import random
    random.seed(0)
    for _ in range(100):
        n = random.randint(1, 12)
        s = ''.join(random.choice('abc') for _ in range(n))
        brute = len({s[i:j] for i in range(n) for j in range(i + 1, n + 1)})
        assert count_distinct_substrings(s) == brute, s
        occ = {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}
        mo = max(sum(1 for i in range(n - len(t) + 1) if s[i:i + len(t)] == t) for t in occ)
        assert max_occurrence(s) == mo, (s, max_occurrence(s), mo)
        # LCS 对拍
        m = random.randint(1, 12)
        t = ''.join(random.choice('abc') for _ in range(m))
        bl = max((len(x) for i in range(len(s)) for j in range(i + 1, len(s) + 1)
                  for x in [s[i:j]] if x in t), default=0)
        assert longest_common_substring(s, t) == bl, (s, t, longest_common_substring(s, t), bl)
    print('suffix-automaton tests passed')

易错点

• link[0]=-1；从 last 上溯补转移时 p=-1 必须终止并连 link[cur]=0
• clone 必须复制 q 的全部转移（字典 copy）与 link，len 重新设置
• 重定向转移时条件是 next[p][c]==q，漏掉条件会把无关转移改坏
• 出现次数统计要按 len 降序（拓扑序），且根不计入 max
• 不同子串数公式对每个非根状态求和；含空串时注意边界
• 最小性：SAM 状态可被 Myhill-Nerode 证明为最少，但实现不一定显式终止状态

例题

信源

• OI Wiki✓ https://oi-wiki.org/string/sam/
• CP-Algorithms✓ https://cp-algorithms.com/string/suffix-automaton.html