本文目录#

后缀自动机简介#

后缀自动机（SAM）是描述所有后缀集合的最小 DFA，支持在 O(|S|) 时间构建、O(|T|) 时间匹配。可用于子串统计、不同子串数量、最长公共子串等问题。

数据结构#

  • link：后缀链接，指向最长合法后缀状态；
  • len：该状态表示的最长串长度；
  • next：状态转移映射。

构建算法#

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
class SuffixAutomaton {
    static class State {
        int len, link;
        Map<Character, Integer> next = new HashMap<>();
    }
    private final List<State> st = new ArrayList<>();
    private int last;

    SuffixAutomaton(String s) {
        st.add(new State());
        last = 0;
        for (char c : s.toCharArray()) extend(c);
    }

    private void extend(char c) {
        int cur = st.size();
        State state = new State();
        state.len = st.get(last).len + 1;
        st.add(state);

        int p = last;
        while (p >= 0 && !st.get(p).next.containsKey(c)) {
            st.get(p).next.put(c, cur);
            p = st.get(p).link;
        }
        if (p == -1) {
            state.link = 0;
        } else {
            int q = st.get(p).next.get(c);
            if (st.get(p).len + 1 == st.get(q).len) {
                state.link = q;
            } else {
                int clone = st.size();
                State cloned = new State();
                cloned.len = st.get(p).len + 1;
                cloned.next.putAll(st.get(q).next);
                cloned.link = st.get(q).link;
                st.add(cloned);
                while (p >= 0 && st.get(p).next.get(c) == q) {
                    st.get(p).next.put(c, clone);
                    p = st.get(p).link;
                }
                st.get(q).link = cloned.link = clone;
                state.link = clone;
            }
        }
        last = cur;
    }

    boolean contains(String t) {
        int v = 0;
        for (char c : t.toCharArray()) {
            Integer nxt = st.get(v).next.get(c);
            if (nxt == null) return false;
            v = nxt;
        }
        return true;
    }
}

应用#

  • 不同子串数量：sum(len[v] - len[link[v]])；
  • 最长公共子串：在 SAM 上匹配另一个串；
  • 出现次数统计：拓扑排序计算 state 的出现次数。

自检清单#

  • 是否在构建完成后通过拓扑顺序传播状态计数？
  • 是否使用数组而非 Map 以提升常数（若字符集小）？
  • 是否考虑内存占用（O(n)）且清理资源？

参考资料#

本作品系原创，采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，转载请注明出处。