参考博客：【学习笔记】字符串—广义后缀自动机
基础部分：后缀自动机SAM)
广义后缀自动机适用于多串的子串问题。它的DFA可以识别多串中的任意一个子串。同时也有类似 SAM 的一些性质。
知识精要
广义SAM 的建立
根据参考博客所说，有好几种 假 写法。比如：每一个串的开头设置 lst) 为 1)；多串拼成一个大串，中间用’#’连接 等等；
正规写法：
离线做法
建出所有串的 Trie) 树。然后在 Trie) 上 bfs) ，每次将一个字符加到其 Trie) 的 fa) 上。其余与 SAM 同。
t_c[cur]:Trie) 上的 cur) 节点的父亲节点
pos[cur]:Trie) 上的 cur) 节点（所代表子串)在 SAM 上的位置
int insint c, int lst):) 几与普通SAM同。传入 lst)，传出 np)
Code:)
inline void work) {
for register int c = 0; c < 26; ++c)
if trie[1][c]) que[++rear] = trie[1][c];
pos[1] = 1;
while front < rear) {
int cur = que[++front];
pos[cur] = inst_c[cur], pos[t_fa[cur]]);
for register int c = 0; c < 26; ++c)
if trie[cur][c]) que[++rear] = trie[cur][c];
}
}
在线做法
每一个串的开头设置 lst) 为 1)。但是由于一开始可能就存在 son[lst][c])，那就不太妙。因此需要加两个特判：
特判一
if son[lst][c] && len[son[lst][c]] == len[lst] + 1) return son[lst][c];
如果有一个完美的节点 q)，那么我们直接将 lst) 设置为这个点返回即可。
特判二
//...
//if len[q] == len[p] + 1) return ...
if p == lst) flag = true;
//int nq = ++tot; len[nq]...
如果存在一个不那么完美的节点 q)，那么我们可以新建一个节点 nq)，然后…（同SAM）。这样我们就和普通 SAM 合并一下，在最后判断一下，如果是这种情况，就直接返回 nq) 即可。可以证明的是，此时建立的 p) 节点是一个“空点”，因为 len[p] = len[lst] + 1, minlen[p] = len[nq] + 1 = len[lst] + 2)。
代码
inline int insint c, int lst) {
if son[lst][c] && len[son[lst][c]] == len[lst] + 1) return son[lst][c];
int np = ++tot, p = lst;
len[np] = len[p] + 1;
while p && !son[p][c]) son[p][c] = np, p = fa[p];
if !p) return fa[np] = 1, np;
int q = son[p][c];
if len[q] == len[p] + 1) return fa[np] = q, np;
bool flag = false;
if p == lst) flag = true;
int nq = ++tot; len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
memcpyson[nq], son[q], sizeofson[q]));
while p && son[p][c] == q) son[p][c] = nq, p = fa[p];
return flag ? nq : np;
}
在线做法由于空间开得小，码量也小，一般使用在线做法，但是离线做法的思想也要知道。
在建立广义SAM的同时，还可以维护每个串的 endpos) 集合，应用 len) 的性质等等。具体见下方。
技能展示
识别某串是否是多串中某串的子串
直接建广义SAM，在DFA上跑即可。
多串中本质不同子串个数
建广义SAM，ans = sum{len[i] – len[fa[i]]})
维护每个串的 endpos) 集合
在加入ins))时，对于表示当前串的节点 的siz) 赋值为 1。（注意特判的地方，如果找到了个“完美的替身”，那么让替身的 siz) 为1；如果确实要让nq代替np，那么将np的siz的那个1转移给nq）然后再按照类似普通SAM的做法搞出 endpos) 集合。（搞firstpos)后线段树合并）
求多串最长公共子串
SP1812 LCS2 – Longest Common Substring II
建立多串的广义SAM，同时维护每个串的 endpos) 集合（大小）。最后检查每个节点是否“被所有节点共同拥有”。如果有这样的节点，那么可以用这个节点的 len) 更新答案。
例题
#3473. 字符串
调到心态爆炸，暂时放弃。
记录在这里：my record
附
模板（调试用）
inline int insint c, int lst) {
if son[lst][c] && len[son[lst][c]] == len[lst] + 1) return son[lst][c];
int np = ++tot, p = lst;
len[np] = len[p] + 1;
while p && !son[p][c]) son[p][c] = np, p = fa[p];
if !p) return fa[np] = 1, np;
int q = son[p][c];
if len[q] == len[p] + 1) return fa[np] = q, np;
bool flag = false;
if p == lst) flag = true;
int nq = ++tot; len[nq] = len[p] + 1;
fa[nq] = fa[q], fa[q] = fa[np] = nq;
memcpyson[nq], son[q], sizeofson[q]));
while p && son[p][c] == q) son[p][c] = nq, p = fa[p];
return flag ? nq : np;
}
Continued…