终于学 \(\text{GSAM}\) 了，这是一个非常有意思且精美的结构！
对于一颗 \(\text{Trie}\) 树 \(T\)，我们可以跟处理普通字符串一样定义出它的“前缀”（根到某点的字符串），“后缀”（某点到叶子的字符串），“子串”（一条直链对应的字符串）。而它的后缀自动机被定义为接受它所有后缀的最小 \(\text{DFA}\)。
我们仿照 \(\text{SAM}\) 的定义定义出 \(\text{endpos}\) 集合，那么可以仿照单串后缀自动机的证明说明这是一个树形结构。同时在新增一个叶节点后等价类分裂的方式大体与普通的后缀自动机相同。具体证明可以参考刘研绎 2015 年的集训队论文。
广义后缀自动机的节点数可以套用后缀自动机的两种方法（$\texttt{OI-wiki} 都提到了）证明它是
也就是说，仅仅是写出代码来说，建立 \(\text{GSAM}\) 跟建立 \(\text{SAM}\) 过程大体一样！
下面是一种离线 \(\text{bfs}\) 的写法。
int tr[N][10],len[N],link[N],cnt=1;
int ch[N][10],pos[N],rk=1;
int que[N],tl;
namespace BFS{
int extend(int c,int p){
int cur=++cnt;
len[cur]=len[p]+1;
while(p&&!tr[p][c]) tr[p][c]=cur,p=link[p];
if(p){
int q=tr[p][c];
if(len[q]==len[p]+1) link[cur]=q;
else{
int clone=++cnt;
memcpy(tr[clone],tr[q],lm<<2);
len[clone]=len[p]+1;
link[clone]=link[q];
link[cur]=link[q]=clone;
while(p&&tr[p][c]==q) tr[p][c]=clone,p=link[p];
}
}
else link[cur]=1;
return cur;
}
void solve(){
que[tl=1]=1;
for(int ps=1;ps<=tl;++ps){
int u=que[ps];
for(int c=0;c<lm;++c)
if(ch[u][c]){
pos[ch[u][c]]=extend(c,pos[u]);
que[++tl]=ch[u][c];
}
}
}
}
我们注意到与原版 \(\text{SAM}\) 的唯一区别就是在 \(\text{las}\) 节点继承方面，\(\text{GSAM}\) 需要直接继承 \(\text{Trie}\) 上的父亲。
可为什么一定要用 \(\text{bfs}\) 呢？有两个很重要的理由，暂且按下不表。
事实上我们还有一种 \(\text{dfs}\) 的写法，它在某些方面更有优势，比如它支持在线插入一个模式串。
int tr[N][10],len[N],link[N],cnt=1;
int ch[N][10],pos[N],rk=1;
namespace DFS{
int extend(int c,int p){
if(tr[p][c]){
int q=tr[p][c];
if(len[q]==len[p]+1) return q;
int clone=++cnt;
memcpy(tr[clone],tr[q],lm<<2);
len[clone]=len[p]+1;
link[clone]=link[q];
link[q]=clone;
while(p&&tr[p][c]==q) tr[p][c]=clone,p=link[p];
return clone;
}
int cur=++cnt;
len[cur]=len[p]+1;
while(p&&!tr[p][c]) tr[p][c]=cur,p=link[p];
if(p){
int q=tr[p][c];
if(len[q]==len[p]+1) link[cur]=q;
else{
int clone=++cnt;
memcpy(tr[clone],tr[q],lm<<2);
len[clone]=len[p]+1;
link[clone]=link[q];
link[cur]=link[q]=clone;
while(p&&tr[p][c]==q) tr[p][c]=clone,p=link[p];
}
}
else link[cur]=1;
return cur;
}
void solve(int u=1){
for(int c=0;c<lm;++c)
if(ch[u][c]){
pos[ch[u][c]]=extend(c,pos[u]);
solve(ch[u][c]);
}
}
}
注意到 \(\text{dfs}\) 的区别除了是按深度优先序建立的，而且代码中还多了一块特判。
这是为什么呢？因为在插入新的前缀节点 \(S+x\) 时，在原先的 \(\text{Trie}\) 树上可能已经出现过形如 \(\dots+S+x\) 这样的串，此时代码中的 \(q\) 会指向原先的 \(S+x\) 所在的等价类，将该等价类分裂后会得到一个 \(\text{maxlen}=|S|+1\) 的新等价类，此时如果我们新建了一个 \(\text{cur}\) 指向这个新等价类，那么 \(\text{cur}\) 所在的等价类表示的就是一个空串，与 \(\text{DFA}\) 的最小性不符！
解决方法很简单：如果已经有了 \(S+x\) 这个串，不新建节点就行了！
为什么 \(\text{bfs}\) 没有这个问题呢？因为 \(\dots+S+x\) 不可能在 \(S\) 之前被插入！这是 \(\text{bfs}\) 的第一个优势。
第二个优势是可以证明（具体我也不太会证），\(\text{bfs}\) 的复杂度是关于 \(|T|\) 也就是 \(\text{Trie}\) 的节点数线性（带字符集常数），这样遇到直接给一个 \(\text{Trie}\) 树的题，\(\text{bfs}\) 写法复杂度才对！
而 \(\text{dfs}\) 写法可以看作将若干个模式串分别插入 \(\text{GSAM}\) 的在线算法，套用普通 \(\text{SAM}\) 的关于跳 \(\text{link}\) 次数的势能分析，我们可以知道它关于 \(O(\sum |s_i|)\) 线性（有字符集常数）。所以大多数情况下不需要考虑复杂度问题。
我们可以构造一颗这样的 \(\text{Trie}\) 来达到 \(\text{dfs}\) 写法的上界：构造一条直链，上面转移边全 \(\texttt{a}\)，然后每个点伸出一条转移边 \(\texttt{b}\)，这样每次 \(\text{dfs}\) 到 \(b\) 时都需要跳线性次 \(\text{link}\) 来给纯 \(\texttt{a}\) 等价类添加转移边。