终于学 \(\text{GSAM}\) 了，这是一个非常有意思且精美的结构！
对于一颗 \(\text{Trie}\) 树 \(T\)，我们可以跟处理普通字符串一样定义出它的“前缀”（根到某点的字符串），“后缀”（某点到叶子的字符串），“子串”（一条直链对应的字符串）。而它的后缀自动机被定义为接受它所有后缀的最小 \(\text{DFA}\)。
我们仿照 \(\text{SAM}\) 的定义定义出 \(\text{endpos}\) 集合，那么可以仿照单串后缀自动机的证明说明这是一个树形结构。同时在新增一个叶节点后等价类分裂的方式大体与普通的后缀自动机相同。具体证明可以参考刘研绎 2015 年的集训队论文。
也就是说，仅仅是写出代码来说，建立 \(\text{GSAM}\) 跟建立 \(\text{SAM}\) 过程大体一样！
下面是一种离线 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}\) 呢？有两个很重要的理由，暂且按下不表。
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]);
}
}
}