字符串

字符串，就是由字符连接而成的序列。

常见的字符串问题包括字符串匹配问题、子串相关问题、前缀/后缀相关问题、回文串相关问题、子序列相关问题等。

字符串哈希

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

双值哈希 / 前缀哈希序列

令 f_i(s) = f(s[1..i]) 为字符串 s 的前缀哈希序列，预处理字符串 s 的前缀哈希序列。

constexpr u64 M = 1e9 + 7, M2 = (u64) 1e16 + 61, B = 133;
vector<u64> hs1(n + 2), hs2(n + 2);
for (int i = 1; i <= n; i++) {
    hs1[i] = (hs1[i - 1] * B + s[i - 1]) % M;
    hs2[i] = (hs2[i - 1] * B + s[i - 1]) % M2;
}

获取子串哈希值

注意到 f(s[l + 1..r]) = f_r(s) − f_l(s) × b^r − l 。

其中 b^r − l 可以 O(n) 的预处理出来然后 O(1) 的回答每次询问。

对于回文子串问题，可以预处理字符串 s 与其反转字符串的前缀哈希序列，并 O(1) 的判断回文子串。

注意下列实现中查询区间左开右闭，即查询 f(s[l + 1..r])。

vector<u64> b1(n + 2, 1), b2(n + 2, 1)
for (int i = 1; i <= n; i++) {
    b1[i] = b1[i - 1] * B % M;
    b2[i] = b2[i - 1] * B % M2;
}

u64 h1 = (hs1[r] - hs1[l] * b1[r - l] % M + M) % M;
u64 h2 = (hs2[r] - (u128) hs2[l] * b2[r - l] % M2 + M2) % M2;

前缀函数

定义 border 为字符串一对相同的真前缀与真后缀，定义字符串 pat 的前缀函数值 π[i] 为前缀 i 的最长 border 长度。特别地，π[0] = 0 。

如果前缀 i 的有长度为 len 的 border ，则该前缀长度仅次于 len 的第二长 border 长度为 π[len − 1] ，通过不断地令 len = π[len − 1] 可遍历所有 border 长度。

利用前缀函数的性质可以解决一下问题：

1. 字符串的所有周期：由 s 有长度为 r 的 border 可推出 |s|−r 为 s 的一个周期，通过遍历所有 border 长度，可以确定所有周期。
2. 字符串的最小周期：最长 border 确定最小周期，即 n − π[n − 1] 为 s 的最小周期。
3. 字符串压缩： 令最短周期 k = n − π[n − 1]，且 n 能被 k 整除，则字符串可由长度为 k 的子串重复拼接表示，否则不存在一个有效的压缩。
4. 统计每个前缀的出现次数：通过每个后缀的 π[i] 为其最长 border 设置初始值，然后逆向递推 ans[pre[i - 1]] += ans[i] ，再加上每个前缀本身即可。
5. 一个字符串中本质不同子串的数目：利用前缀函数增量计算，每次添加新字符时，新增的不同子串数目为 (i + 1) − π[i]。

以下代码可以在 O(n) 的时间复杂度内处理出字符串 pat 的前缀函数 pi。

vector<int> pi;  
  
void init(const string &pat) {  
    int n = pat.size();  
    pi.resize(n);  
    for (int i = 1, j = 0; i < n; i++) {  
        while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];  
        if (pat[i] == pat[j]) j++;  
        pi[i] = j;  
    }  
}

KMP 算法

在预处理出模式串 pat 的前缀函数 pi 后，查询模式串在文本中的所有匹配位置（即匹配子串的末位置），时间复杂度 O(n + m) 。

vector<int> kmp(const string &txt, const string &pat) {  
    vector<int> res;  
    int n = pat.size();  
    for (int i = 0, j = 0; i < txt.size(); i++) {  
        while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];  
        if (txt[i] == pat[j]) j++;  
        if (j == n) res.push_back(i), j = pi[j - 1];  
    }  
    return res;  
}

KMP 自动机

通过 KMP 的转移，可以构建一个自动机，其状态为当前的前缀函数值 j，而从一个状态到另一个状态的转移则由下一个字符确定，匹配全串后的状态（即接受状态）为 |s| 。

通过构建该自动机及合理保存不仅可以解决动态的匹配问题（如树上匹配），还可以解决在通过一些规则构造的巨型字符串上的匹配问题，即定义 G[i][s] 为状态 i 接受特殊字符串 s 后的状态，然后通过字符串构建规则转移该自动机与统计答案。

vector<vector<int>> aut;  
  
void compute(string s) {  
    s += '#';  
    int n = s.size();  
    aut.assign(n, vector<int>(26));  
    for (int i = 0; i < n; i++) {  
        for (int c = 0; c < 26; c++) {  
            if (i > 0 && 'a' + c != s[i]) aut[i][c] = aut[pi[i - 1]][c];  
            else aut[i][c] = i + ('a' + c == s[i]);  
        }  
    }  
}

Manacher 算法

Manacher 算法可以在 Θ(n) 的时间内处理出回文半径数组，原字符串下标 i 的字符对应新字符串下标 i * 2 + 1 ，回文串判断函数左闭右闭实现。

vector<int> p;
auto manacher = [&](const string &str) {
    string t = "#";
    for (char ch: str) t += ch, t += "#";
    p.resize(t.size());
    int len = (int) t.size(), c = 0, r = 0;
    for (int i = 1; i < len - 1; ++i) {
        if (i < r) p[i] = min(r - i, p[2 * c - i]);
        while (i + p[i] + 1 < len && i - p[i] - 1 >= 0 && t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;
        if (i + p[i] > r) c = i, r = i + p[i];
    }
};
manacher(s);

auto palindromic = [&](int l, int r) {
    return p[l + r + 1] >= r - l + 1;
}

字典树

一个像字典一样的树，用边来代表字符，从根结点到树上某一结点的路径就代表了一个字符串。将结点视为状态，则字典树可以看作一种自动机。

普通字典树

一个动态开点的普通字典树，维护了边数 sz 、结点对应字符串的数量 cnt 和结点对应字符串作为前缀的字符串 pre 数量，其中 get 函数定义了字符到编号的转换。

支持新增字符串、删除字符串与查询字符串在 Trie 上对应结点（不存在则返回 0），单次操作时间复杂度均为 O(L) ，插入操作空间复杂度 O(ΣL) ，其中 L 为字符串长度，Σ 为字符集大小。

注意 array 的动态开点需求 c++17，若版本不足需要改为 vector 实现，或在构造函数提前开好足量 ch 数组大小，并修改 create 函数。

struct Trie {  
    int sz;  
    vector<array<int, 26> > ch;  
    vector<int> pre, cnt;  
  
    explicit Trie() : ch(1), pre(1), cnt(1) {  
        sz = 0;  
    }  
  
    static int id(char c) {  
        return c - 'a';  
    }  
  
    int create() {  
        int x = ch.size();  
        ch.emplace_back();  
        pre.push_back(0);  
        cnt.push_back(0);  
        return x;  
    }  
  
    void insert(const string &s) {  
        int p = 0;  
        pre[p]++;  
        for (char c: s) {  
            int i = id(c);  
            if (!ch[p][i]) ch[p][i] = create();  
            p = ch[p][i];  
            sz += pre[p]++ == 0;  
        }  
        cnt[p]++;  
    }  
  
    void remove(const string &s) {  
        int p = 0;  
        --pre[p];  
        for (char c: s) {  
            int i = id(c);  
            p = ch[p][i];  
            sz -= --pre[p] == 0;  
        }  
        --cnt[p];  
    }  
  
    int find(const string &s) {  
        int p = 0;  
        for (char c: s) {  
            int i = id(c);  
            if (!ch[p][i]) return 0;  
            p = ch[p][i];  
        }  
        return p;  
    }  
};

01 字典树

将数的二进制表示看做一个字符串，就可以建出字符集为 {0, 1} 的 trie 树。

insert(u, x, k) 表示向以 u 节点为根的字典树中插入 k 个值 x 。

query(u, x) 表示在 u 节点为根的字典树中贪心以查询字典树中的值异或上 x 后的最大值 。

struct Trie {  
    static constexpr int mxb = 30;  
      
    vector<array<int, 2> > ch;  
    vector<int> pre;  
  
    Trie() : ch(1), pre(1) {  
    }  
  
    int create() {  
        int x = ch.size();  
        ch.emplace_back();  
        pre.push_back(0);  
        return x;  
    }  
  
    void insert(int u, int x, int k) {  
        pre[u] += k;  
        for (int i = mxb; i >= 0; i--) {  
            int b = x >> i & 1;  
            if (!ch[u][b]) ch[u][b] = create();  
            pre[ch[u][b]] += k;  
            u = ch[u][b];  
        }  
    }  
  
    int query(int u, int x) const {  
        int res = 0;  
        for (int i = mxb; i >= 0; i--) {  
            int b = x >> i & 1;  
            if (pre[ch[u][b ^ 1]]) {  
                u = ch[u][b ^ 1], res |= 1 << i;  
            } else {  
                u = ch[u][b];  
            }  
        }  
        return res;  
    }  
};

AC 自动机

AC（Aho–Corasick）自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的自动机。沿文本串 s 的字符顺序在 AC 自动机转移到的状态对应 s 在 Trie 中的最长匹配后缀。

以下实现基于动态开点的普通字典树，包含插入所有模式串和查询字符串在 Trie 上对应结点，复杂度同普通字典树。

调用 build() 对 Trie 树上所有的结点 p 构造失配指针 fa[p]（在 Trie 的结点中的最长真后缀），同时在 Trie 的基础上构建失配树的邻接表 adj 和 AC 自动机的邻接表 ch 。

调用 dfs(0) 以对所有的结点 p 构建后缀链接 lk[p] ，代表 p 所对应的字符串在所有模式串（即 cnt 非 0 的串）中的最长真后缀。

调用 match(s) 对文本串 s 执行匹配，采用暴力跳 lk 指针统计答案，总复杂度 $O(S\sqrt{T})$ ，其中 S 为文本串长度，但该复杂度通常不紧，常数较小。

设匹配串总长度为 T ，由于每个结点 p 对应的所有匹配串长度均不同，s 的任意位置匹配的模式串个数为 $O(\sqrt{T})$ ，即任意结点 p 跳后缀链接 lk 的次数为 $O(\sqrt{T})$ ，优于跳 fa 指针的 O(T)。

在一些特殊的问题上可以修改 match 统计答案的方式，再修改 dfs 函数以沿着失配树 DP 达到线性复杂度统计答案，如匹配多模式串时状态 p 对所有失配树上的所有祖先有匹配次数 +1，则可先记录 p 结点匹配次数，再在失配树上 DP 求每个结点的子树中匹配次数和。

struct ACAutomaton {  
    vector<array<int, 26> > ch;  
    vector<vector<int> > adj;  
    vector<int> cnt, ans, fa, lk;  
  
    ACAutomaton() : ch(1), adj(1), cnt(1), ans(1), fa(1), lk(1) {  
    }  
  
    static int id(char c) {  
        return c - 'a';  
    }  
  
    int create() {  
        int x = ch.size();  
        ch.emplace_back();  
        adj.emplace_back();  
        cnt.push_back(0);  
        ans.push_back(0);  
        fa.push_back(0);  
        lk.push_back(0);  
        return x;  
    }  
  
    void insert(const string &s) {  
        int p = 0;  
        for (char c: s) {  
            int i = id(c);  
            if (!ch[p][i]) ch[p][i] = create();  
            p = ch[p][i];  
        }  
        cnt[p]++;  
    }  
  
    int find(const string &s) {  
        int p = 0;  
        for (char c: s) {  
            int i = id(c);  
            if (!ch[p][i]) return 0;  
            p = ch[p][i];  
        }  
        return p;  
    }  
  
    void build() {  
        queue<int> q;  
        for (int p: ch[0]) {  
            if (!p) continue;  
            q.push(p);  
            adj[0].push_back(p);  
        }  
        while (!q.empty()) {  
            int u = q.front();  
            q.pop();  
            for (int i = 0; i < 26; i++) {  
                int &p = ch[u][i];  
                if (p) {  
                    adj[ch[fa[u]][i]].push_back(p);  
                    fa[p] = ch[fa[u]][i];  
                    q.push(p);  
                } else {  
                    p = ch[fa[u]][i];  
                }  
            }  
        }  
    }  
  
    void dfs(int u) {  
        for (int v: adj[u]) {  
            lk[v] = cnt[u] ? u : lk[u];  
            dfs(v);  
            // ans[u] += ans[v];  
        }  
    }  
  
    void match(const string &s) {  
        int p = 0;  
        for (char c: s) {  
            p = ch[p][id(c)];  
            // ans[p]++;  
            for (int i = p; i; i = lk[i]) ans[i]++;  
        }  
    }  
};

后缀数组

后缀数组是一种将字符串所有后缀按字典序排序的字符串数据结构，以下经典问题均可以使用后缀数组解决：

1. 两子串最长公共前缀：直接使用 SA 的 LCP 数组结合 RMQ 快速查询任意两后缀的 LCP 。
2. 两子串的大小关系：假设需要比较的是 A = S[a..b] 和 B = S[c..d] 的大小关系，若 lcp(a, c) ≥ min (|A|,|B|) ，A < B ⇔ |A| < |B| ，否则，A < B ⇔ rk[a] < rk[c] 。
3. 不同子串的数目：总子串数减去相邻后缀的 LCP 之和，即 $\frac{n(n+1)}{2} - \sum\text{ht}[i]$ 。
4. 两串最长公共子串：拼接两字符串并加分隔符，在后缀数组上属于不同串的相邻后缀的 LCP 的最大值即为答案。
5. 多串最长公共子串：拼接所有串并加分隔符，在 SA 上滑动窗口求包含所有串的区间的多串 LCP 最大值。
6. 出现至少 k 次的子串的最大长度：出现至少 k 次意味着后缀排序后有至少连续 k 个后缀以这个子串作为公共前缀，求出每相邻 k − 1 个 ht 的最小值，再求这些最小值的最大值就是答案，可以使用滑动窗口解决。
7. 字符串循环移位最小表示：将字符串复制一份接在后面，构建 SA 后找首个长度 ≥n 的后缀起始位置。
8. 在字符串中在线找子串：先构造出 txt 的后缀数组，我们可以通过在 sa 数组中二分并暴力比较后缀与模式串 pat ，找到其出现位置，总时间复杂度为 O(|S|log |T|)，出现次数可以通过再次二分找到。

以上只是后缀数组所能解决的问题中的一小部分，在使用后缀数组时，常常从以下角度思考：

• 对子串问题，任何子串都是某个后缀的前缀，将对子串操作转化为对后缀的操作。
• 多字符串问题，可拼接字符串并用唯一分隔符隔开（如 S1#S2$），转化为子串问题。
• 涉及最大化匹配与公共前缀问题，考虑 sa 上的相邻串。
• 涉及字典序的比较，考虑串在 sa 数组的先后顺序。
• 涉及 LCP 的比较，考虑 ht 数组求 RMQ 带来的单调性。

从 SA 数组上的性质出发，结合其它算法或数据结构，可以解决更复杂的字符串问题：

某些题目求解时要求你将后缀数组划分成若干个连续 LCP 长度大于等于某一值的段，我们只需将查询离线并要维护一个并查集，每次合并相邻的两个区间，并维护统计信息。

某些题目让你求满足条件的前若干个数，而这些数又在后缀排序中的一个区间内，可以用归并排序的性质来合并两个结点的信息，利用线段树维护和查询区间答案。

倍增 + 基数排序法求后缀数组

以下代码使用倍增算法和基数排序构建后缀数组，总构建复杂度 O(nlog n) 。

struct SuffixArray {  
    int n;  
    vector<int> sa, rk;  
  
    explicit SuffixArray(const string &s) : n(s.size()), sa(n), rk(n) {  
        iota(sa.begin(), sa.end(), 0);  
        sort(sa.begin(), sa.end(), [&](int a, int b) { return s[a] < s[b]; });  
        for (int i = 1; i < n; i++) rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);  
        vector<int> tmp(n), cnt(n);  
        for (int k = 1; rk[sa[n - 1]] < n - 1; k <<= 1) {  
            tmp.clear();  
            for (int i = 0; i < k; i++) tmp.push_back(n - k + i);  
            for (auto i: sa) if (i >= k) tmp.push_back(i - k);  
            fill(cnt.begin(), cnt.end(), 0);  
            for (int i = 0; i < n; i++) cnt[rk[i]]++;  
            for (int i = 1; i < n; i++) cnt[i] += cnt[i - 1];  
            for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i];  
            swap(rk, tmp);  
            rk[sa[0]] = 0;  
            for (int i = 1; i < n; i++) {  
                int inc = tmp[sa[i - 1]] != tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] != tmp[sa[i] + k];  
                rk[sa[i]] = rk[sa[i - 1]] + inc;  
            }  
        }  
    }  
};

LCP 数组

这段代码实现了一个基于后缀数组的 LCP 数组，支持快速查询任意两个后缀的 LCP 长度，其中 ht[i] = lcp(sa[i], sa[i + 1]) ，注意 rmq 函数使用左闭右开实现，预处理时间复杂度为 O(nlog n)，查询时间复杂度为 O(1) 。

struct LCPArray {  
    int n;  
    SuffixArray sa;  
    vector<int> ht;  
    vector<vector<int> > st;  
  
    explicit LCPArray(const string &s) : n(s.size()), sa(s), ht(n - 1), st(__lg(n - 1) + 1, vector<int>(n - 1)) {  
        if (n <= 1) return;  
        for (int i = 0, j = 0; i < n; i++) {  
            if (sa.rk[i] == 0) continue;  
            for (j -= j > 0; i + j < n && sa.sa[sa.rk[i] - 1] + j < n && s[i + j] == s[sa.sa[sa.rk[i] - 1] + j]; j++) {  
            }  
            ht[sa.rk[i] - 1] = j;  
        }  
        st[0] = ht;  
        for (int j = 1; j <= __lg(n - 1); j++) {  
            for (int i = 0; i + (1 << j) <= n - 1; i++) {  
                st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);  
            }  
        }  
    }  
  
    int rmq(int l, int r) {  
        if (l >= r) return 0;  
        int k = __lg(r - l);  
        return min(st[k][l], st[k][r - (1 << k)]);  
    }  
  
    int lcp(int i, int j) {  
        if (i == j || i == n || j == n) return min(n - i, n - j);  
        int a = sa.rk[i], b = sa.rk[j];  
        if (a > b) swap(a, b);  
        return min({n - i, n - j, rmq(a, b)});  
    }  
};

SA-IS 算法

SA-IS 算法是一种线性时间构造后缀数组的算法，核心思想是通过诱导排序和递归缩减问题规模实现高效构造。

算法首先将后缀分为两类：L 型后缀（字典序大于后继后缀）和 S 型后缀（字典序小于后继后缀）。特殊地，当 s[i] 为 S 型且 s[i − 1] 为 L 型时，s[i] 称为LMS 后缀（Left-Most S-type）。这些 LMS 后缀将字符串分割为若干 LMS 子串。

算法流程分为三个阶段：首先扫描字符串（从右向左）标记所有后缀类型并记录 LMS 位置。接着通过三重诱导排序初步确定 LMS 子串顺序：

1. 将 LMS 后缀放入对应字符的 S 型桶尾部
2. 从左向右扫描，将 L 型后缀插入对应字符的 L 型桶头部
3. 从右向左扫描，将 S 型后缀插入对应字符的 S 型桶尾部

此时检查 LMS 子串是否全部唯一：若唯一则直接映射为有序序列；否则将 LMS 子串的排名组成新字符串递归处理。递归结果确定 LMS 子串顺序后，再次进行三重诱导排序即可得到完整后缀数组。时间复杂度为 O(n)，递归深度 log n，每层处理 O(n) 时间，满足 T(n) = T(n/2) + O(n) 。

struct SuffixArray {  
    int n;  
    vector<int> sa, rk;  
  
    explicit SuffixArray(const string &s) : n(s.size()), sa(n + 1), rk(n + 1) {  
        vector<int> a(n + 1);  
        for (int i = 0; i < n; i++) a[i] = s[i];  
        sais(a, sa, n + 1, 256);  
        sa.erase(sa.begin());  
        for (int i = 0; i < n; i++) rk[sa[i]] = i;  
    }  
  
    static void sais(const vector<int> &a, vector<int> &sa, int n, int sig) {  
        if (n == 1) return;  
        vector<int> tp(n), lm;  
        for (int i = n - 2; i >= 0; i--) tp[i] = a[i] > a[i + 1] || a[i] == a[i + 1] && tp[i + 1];  
        auto ilm = [&](int i) { return i >= 1 && !tp[i] && tp[i - 1]; };  
        for (int i = 0; i < n; i++) if (ilm(i)) lm.push_back(i);  
  
        vector<int> sum(sig + 1);  
        for (int i = 0; i < n; i++) sum[a[i] + 1]++;  
        for (int i = 1; i <= sig; i++) sum[i] += sum[i - 1];  
        auto induce = [&](const vector<int> &slm) {  
            fill(sa.begin(), sa.end(), -1);  
            vector<int> mbu = sum, lbu = sum, sbu = sum;  
            for (int i = slm.size() - 1; i >= 0; i--)  
                sa[--mbu[a[slm[i]] + 1]] = slm[i];  
            for (int i = 0; i < n; i++)  
                if (sa[i] > 0 && tp[sa[i] - 1])  
                    sa[lbu[a[sa[i] - 1]]++] = sa[i] - 1;  
            for (int i = n - 1; i >= 0; i--)  
                if (sa[i] > 0 && !tp[sa[i] - 1])  
                    sa[--sbu[a[sa[i] - 1] + 1]] = sa[i] - 1;  
        };  
        induce(lm);  
  
        bool flag = false;  
        int cnt = 0, lx = -1;  
        vector<int> nm(n);  
        auto eq = [&](int x, int y) {  
            do {  
                if (a[x] != a[y]) return false;  
                x++, y++;  
            } while (!ilm(x) && !ilm(y));  
            return a[x] == a[y];  
        };  
        for (int i = 0; i < n; i++) {  
            if (!ilm(sa[i])) continue;  
            if (~lx && !eq(lx, sa[i])) cnt++;  
            if (~lx && cnt == nm[lx]) flag = true;  
            nm[sa[i]] = cnt, lx = sa[i];  
        }  
  
        vector<int> slm(lm.size());  
        if (!flag) {  
            for (int x: lm) slm[nm[x]] = x;  
        } else {  
            vector<int> a1(lm.size()), sa1(lm.size());  
            for (int i = 0; i < lm.size(); i++) a1[i] = nm[lm[i]];  
            sais(a1, sa1, a1.size(), cnt + 1);  
            for (int i = 0; i < lm.size(); i++) slm[i] = lm[sa1[i]];  
        }  
        induce(slm);  
    }  
};

后缀自动机

后缀自动机（SAM）是一个接受 s 的所有后缀的最小 DFA （确定性有限状态自动机）。

以下代码实现了动态开点的后缀自动机，维护了等价类最长串长度 len 和后缀链接树的父亲 fa 。

insert 操作均摊时间复杂度为 O(log Σ) ，总空间复杂度 O(n)，其中 Σ 为字符集大小，n 为操作次数。

struct SuffixAutomaton {  
    int las;  
    vector<int> len, fa;  
    vector<map<int, int> > ch;  
  
    explicit SuffixAutomaton(): las(1), len(2), fa(2), ch(2) {  
    }  
  
    int create() {  
        int x = ch.size();  
        len.push_back(0);  
        fa.push_back(0);  
        ch.emplace_back();  
        return x;  
    }  
  
    void insert(int i) {  
        int p = las, np = las = create();  
        len[np] = len[p] + 1;  
        for (; p && !ch[p].contains(i); p = fa[p]) ch[p][i] = np;  
        if (!p) {  
            fa[np] = 1;  
        } else {  
            int q = ch[p][i];  
            if (len[q] == len[p] + 1) {  
                fa[np] = q;  
            } else {  
                int nq = create();  
                len[nq] = len[p] + 1;  
                fa[nq] = fa[q];  
                ch[nq] = ch[q];  
                fa[q] = fa[np] = nq;  
                for (; p && ch[p].contains(i) && ch[p][i] == q; p = fa[p]) ch[p][i] = nq;  
            }  
        }  
    }  
};

子串出现次数

节点 u 表示的串的 endpos 大小就是后缀连接树上 u 子树中的前缀点数量。

以下实现使用桶排序得到节点拓扑顺序，并按拓扑序 dp 得到每个等价类的子串出现次数，时间复杂度 O(n) 。

SuffixAutomaton sam;  
vector<int> pren(s.size());  
for (int i = 0; i < s.size(); i++) {  
    sam.insert(s[i]);  
    pren[i] = sam.las;  
}

int maxl = sam.len[sam.las], tot = sam.ch.size() - 1;  
vector<int> bu(maxl + 1), tp(tot + 1);  
for (int i = 1; i <= tot; i++) bu[sam.len[i]]++;  
for (int i = 1; i <= maxl; i++) bu[i] += bu[i - 1];  
for (int i = 1; i <= tot; i++) tp[bu[sam.len[i]]--] = i;  
  
vector<i64> cnt(tot + 1);  
for (int i = 0; i < s.size(); i++) cnt[pren[i]] = 1;  
for (int i = tot; i >= 2; i--) cnt[sam.fa[tp[i]]] += cnt[tp[i]];  
cnt[1] = 0;