广义后缀自动机略记

终于学 \(\text{GSAM}\) 了，这是一个非常有意思且精美的结构！

对于一颗 \(\text{Trie}\) 树 \(T\)，我们可以跟处理普通字符串一样定义出它的“前缀”（根到某点的字符串），“后缀”（某点到叶子的字符串），“子串”（一条直链对应的字符串）。而它的后缀自动机被定义为接受它所有后缀的最小 \(\text{DFA}\)。

我们仿照 \(\text{SAM}\) 的定义定义出 \(\text{endpos}\) 集合，那么可以仿照单串后缀自动机的证明说明这是一个树形结构。同时在新增一个叶节点后等价类分裂的方式大体与普通的后缀自动机相同。具体证明可以参考刘研绎 2015 年的集训队论文。

也就是说，仅仅是写出代码来说，建立 \(\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}\) 的节点数线性（带字符集常数），