后缀自动机 SAM

模板

struct SAM {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        array<int, ALPHABET_SIZE> next;
        Node() : len{}, link{}, next{} {}
    };
    vector<Node> t;
    SAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c) {
        if (t[p].next[c]) {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1) {
                return q;
            }
            int r = newNode();
            t[r].len = t[p].len + 1;
            t[r].link = t[q].link;
            t[r].next = t[q].next;
            t[q].link = r;
            while (t[p].next[c] == q) {
                t[p].next[c] = r;
                p = t[p].link;
            }
            return r;
        }
        int cur = newNode();
        t[cur].len = t[p].len + 1;
        while (!t[p].next[c]) {
            t[p].next[c] = cur;
            p = t[p].link;
        }
        t[cur].link = extend(p, c);
        return cur;
    }
    int extend(int p, char c, char offset = 'a') {
        return extend(p, c - offset);
    }

    int next(int p, int x) {
        return t[p].next[x];
    }

    int next(int p, char c, char offset = 'a') {
        return next(p, c - 'a');
    }

    int link(int p) {
        return t[p].link;
    }

    int len(int p) {
        return t[p].len;
    }

    int size() {
        return t.size();
    }
};

部分原理

SAM 的树形结构

每个节点 i 代表着一个 endpos，len(i) 就是这个 endpos 中长度最大的子串长度。从 link(i) -> i 有一条边，这条边指向了下一级的“细化”，即 i 是 link(i) 这个点代表的 endpos 中最长的那个子串，在前方又加了一个字符之后的 endpos。

如果只考虑从 link(i) -> i 连边，会形成一颗真的树，这里有性质： len(i) - len(link(i)) == 一部分本质不同的子串，所有点的这个差值加起来，就是整个后缀自动机含有的本质不同子串数。

另一种建图方式是按照 i -> next(i, 0…25) 建图，这得到的类似于一个字典树，但不完全一样，在这张图上，从原点出发，走到任意一个点形成的一个串就是原字符串的一个子串。

以字符串 abcabcabc 为例，其两棵树如下：

8ebd000c30cc74a8d075762d1395d9d0

使用方法

以 ljs 的板子为例！

首先，SAM 的原点是 1，0 号节点只是虚拟凑数用的，用法如下：以统计本质不同子串数为例。

void solve() {
    string s;
    cin >> s;
    SAM sam;
    int p = 1;
    for (int i = 0; i < s.size(); i++) {
        p = sam.extend(p, s[i]);
    }
    int m = sam.size();
    vector<vector<int>> adj(m);
    for (int i = 1; i < m; i++) {
        adj[sam.link(i)].emplace_back(i);
    }
    // 这是 link(i) -> i 的树
    i64 ans = 0;
    auto dfs = [&](auto self, int u, int fa) -> void {
        if (fa) {
            ans += sam.len(u) - sam.len(fa);
        }
        for (auto v : adj[u]) {
            self(self, v, u);
        }
    };
    dfs(dfs, 1, 0);
    // 统计出了本质不同子串数

    vector<int> dp(m);
    auto DFS = [&](auto self, int u, int fa) -> void {
        dp[u] += 1;
        for (int i = 0; i < 26; i++) {
            if (sam.next(u, i) && sam.next(u, i) != fa) {
                if (!dp[sam.next(u, i)]) {
                    // 这里小心，因为这个点不一定被处理过！
                    self(self, sam.next(u, i), u);
                }
                dp[u] += dp[sam.next(u, i)];
            }
        }
    };
    DFS(DFS, 1, 0);
    cout << ans << "\n";
    cout << dp[1] - 1 << "\n";
    // 减一是因为 1 号自己代表空串，也算进去了
}

计算每个节点的 endpos 的大小

首先，对于这个节点代表的一组子串，其每一个出现的位置最终都会扩张成一个前缀。因为字符是一个一个加进来的，所以在那个位置的字符加进来之后，一定会作为当时的 extend 节点被返回。因此，我们把每一次加入字符后的位置标记为 1，建立 link(i) -> i 的树，那么每个结点的子树和就是该节点 endpos 的大小，即该类串出现的次数！！！

子串的出现频率

直接沿着目标串跳边，停在的那个位置的 endpos 就是子串的出现频率

例题，求字典序第 k 小的子串

void solve() {
    string s;
    int t, k;
    cin >> s >> t >> k;
    int n = s.size();
    SAM sam;
    vector<int> pre;
    for (int i = 0, p = 1; i < n; i++) {
        p = sam.extend(p, s[i]);
        pre.emplace_back(p);
    }
    int m = sam.size();
    vector<i64> f(m), g(m);
    for (auto t : pre) {
        f[t] = 1;
    }
    vector<vector<int>> adj(m);
    for (int i = 1; i < m; i++) {
        adj[sam.link(i)].emplace_back(i);
    }
    auto dfs = [&](auto self, int u, int fa) -> void {
        for (auto v : adj[u]) {
            if (v == fa) continue;
            self(self, v, u);
            f[u] += f[v];
        }
    };
    dfs(dfs, 1, 0);
    if (!t) {
        for (int i = 1; i < m; i++) {
            f[i] = min(f[i], 1LL);
        }
    }

    vector<bool> vis(m);

    auto dfs2 = [&](auto self, int u, int fa) -> i64 {
        if (vis[u]) return g[u] + f[u];
        vis[u] = 1;
        for (int i = 0; i < 26; i++) {
            int nex = sam.next(u, i);
            if (!nex) continue;
            g[u] += self(self, nex, u);
        }
        return g[u] + f[u];
    };
    dfs2(dfs2, 1, 0);

    if (g[1] < k) {
        cout << "-1\n";
        return;
    }

    f[1] = g[1] = 0;

    string ans;
    auto DFS = [&](auto self, int u, int fa, int rk) -> void {
        if (rk - f[u] <= 0) return;
        rk -= f[u];
        for (int i = 0; i < 26; i++) {
            int nex = sam.next(u, i);
            if (!nex) continue;
            if (rk - g[nex] - f[nex] > 0) {
                rk -= g[nex] + f[nex];
                continue;
            }
            ans += 'a' + i;
            self(self, nex, u, rk);
            return;
        }
    };

    DFS(DFS, 1, 0, k);
    cout << ans << "\n";
}