广义后缀自动机（Generalized Suffix Automaton, GSA）是一种高效处理多字符串子串问题的数据结构，能够在线性时间内构建并支持多种查询操作。其核心思想是将多个字符串的子串统一建模为一个确定有限自动机（DFA），从而实现对所有字符串中任意子串的快速识别与统计。

构建方式

离线方法：基于 Trie 树的 BFS 遍历

该方法适用于已知所有输入字符串的情况。首先建立这些字符串的公共前缀树（Trie），然后通过广度优先搜索遍历 Trie 节点。对于每个节点，将其对应的字符插入到 SAM 中，并利用父节点的对应状态进行转移。

• trie[u][c] 表示 Trie 树中节点 u 的字符 c 子节点。
• t_c[cur] 为当前节点在 Trie 中的父节点。
• pos[cur] 记录该节点在 SAM 中所对应的节点编号。
• 插入函数 ins(c, lst) 返回新状态的编号，逻辑与标准 SAM 一致。

inline void build_gsam() {
    queue<int> q;
    for (int c = 0; c < 26; ++c)
        if (trie[1][c]) q.push(trie[1][c]);
    pos[1] = 1;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        pos[cur] = ins(t_c[cur], pos[t_fa[cur]]);
        for (int c = 0; c < 26; ++c)
            if (trie[cur][c]) q.push(trie[cur][c]);
    }
}

此方法结构清晰，适合离线处理，但需额外存储 Trie 结构。

在线方法：逐串插入 + 特判优化

在线方式无需预先构造 Trie，可逐个添加字符串。关键在于两个特判以避免重复创建或错误转移：

1. 完美匹配判断 若当前状态 lst 已有边 c 指向长度恰好为 len[lst] + 1 的节点，则直接返回该节点，避免冗余操作。

2. 分裂节点处理 当发现需分裂节点时，引入新节点 nq 作为中间状态，继承原节点 q 的转移信息，并更新父子关系。若当前路径起始于 lst，则说明新节点应作为主节点返回。

inline int insert(int c, int lst) {
    int &next = son[lst][c];
    if (next && len[next] == len[lst] + 1)
        return next;

    int np = ++tot;
    len[np] = len[lst] + 1;
    int p = lst;

    // 延展路径直到无法继续
    while (p && !son[p][c])
        son[p][c] = np, p = fa[p];

    if (!p) {
        fa[np] = 1;
        return np;
    }

    int q = son[p][c];
    if (len[q] == len[p] + 1) {
        fa[np] = q;
        return np;
    }

    bool is_split = (p == lst);
    int nq = ++tot;
    len[nq] = len[p] + 1;
    fa[nq] = fa[q];
    fa[q] = fa[np] = nq;
    memcpy(son[nq], son[q], sizeof(son[q]));

    while (p && son[p][c] == q)
        son[p][c] = nq, p = fa[p];

    return is_split ? nq : np;
}

在线做法空间更紧凑，代码简洁，常用于竞赛环境。

---

常见应用

判断某串是否为任意给定字符串的子串

构建广义 SAM 后，可在自动机上模拟匹配过程，从初始状态出发，按字符依次跳转。若最终能到达某个有效状态，则该串是某个原始串的子串。

统计多串中本质不同的子串总数

利用 SAM 的性质：每个节点贡献的唯一子串数为 len[i] - len[fa[i]]。总和即为答案。

long long distinct_substrings() {
    long long ans = 0;
    for (int i = 2; i <= tot; ++i)
        ans += len[i] - len[fa[i]];
    return ans;
}

维护每串的结束位置集合（endpos）

在每次插入过程中，标记"当前串结尾"的节点 siz 为 1。若发生分裂，则将 np 的 siz 值转移至 nq。最后通过拓扑排序结合线段树合并，还原每个节点的 endpos 集合。

求解多串最长公共子串

目标是寻找被所有字符串共同包含的最长子串。算法步骤如下：

• 构建广义 SAM 并维护每个节点的 endpos 集合大小（记录属于多少个原始串）。
• 遍历所有节点，若某节点的 endpos.size() == 总串数，则该节点代表的子串是公共子串。
• 用最大 len[i] 更新答案。

典型例题：SP1812 LCS2 - Longest Common Substring II

---

实际挑战与调试建议

部分题目如「洛谷 P3473」涉及复杂边界条件，例如多串交替、空串、重复模式等，容易导致状态分裂异常或 siz 值错位。建议在调试时打印关键节点的 len, fa, son[] 和 siz 信息，辅助定位问题。