如何优雅地用SAM构造SA数组

· · 科技·工程

如何优雅地用SAM构造SA数组

阅读前提

能熟练背诵并默写SAM板子，对SAM及其link（或称fail）树有一定的了解。

想法依据：

三个后缀结构之间的关系：

给原串的反串建SAM，相当于对原串建后缀树。

将后缀树按照字典序遍历，dfn序相当于原串的SA数组。

构建算法

首先由于众所周知的原因，SAM是前缀性的，而SA维护的是后缀，所以请自动将原串翻转，并且下文所称的“原串”均为已经翻转的。

首先先将我们的SAM板子拿出来。

struct Sam{
    int ch[N][27],len[N],fai[N],tot,lst;
    vector<int>ifai[N];
    int insert(int c){
        int cur=++tot,p=lst;
        len[cur]=len[p]+1;
        for(;p!=-1&&!ch[p][c];p=fai[p]) ch[p][c]=cur;
        if(p!=-1){
            int q=ch[p][c];
            if(len[p]+1==len[q]) fai[cur]=q;
            else{
                int clone=++tot;
                memcpy(ch[clone],ch[q],sizeof ch[q]);
                fai[clone]=fai[q],len[clone]=len[p]+1;
                for(;p!=-1&&ch[p][c]==q;p=fai[p]) ch[p][c]=clone;
                fai[cur]=fai[q]=clone;
            }
        }
        lst=cur;
    }
    void build(){
        for(int i=1;i<=tot;i++) ifai[fai[i]].push_back(i);
        //dfs(0);
    }
}F;

上面的代码是正常构建SAM及其fail树的流程，我们考虑fail树有一个及其重要的性质：

性质：对于fail树的某一个节点（等价类），它所代表的字符串是其子树内所有等价类代表的字符串的后缀。

于是我们就有以下的引理：

引理：任意两个子串的最长公共后缀，为它们在fail树内代表节点的lca所代表的最长字符串长度。

相信上面的性质已经被各位字符串大爹给用烂了。

那么根据引理和性质，只要我们把fail树中的非clone得到的节点以字典序遍历，按照dfn序放进数组中，就能得到SA数组。

那么现在问题来了，如何确定一个节点中所有儿子的字典序大小？

上图：

如图，u和v是一对父子关系，根据性质和引理可得，u的所有的v的字符‘a’都是不同的，那么我们直接以‘a’为关键字排序儿子即可。

现在问题在于如何对于每一个儿子v求出它对应的‘a’。

以上的问题是简单的，我们通过记录pos[i]表示SAM中i节点代表的等价类的endpos集合中最小的那个元素（大白话来讲，就是它代表的所有字符串，在原串第一次出现的结尾位置），那么对于一个v的a，显然就是S_{pos[v]-len[u]}（S代表原串）。

这样我们就有代码：

struct Sam{
    char s[N<<1];//储存原串
    int ch[N<<1][26],len[N<<1],siz[N<<1],fai[N<<1],pos[N<<1],tot;
    vector<node>ifai[N<<1];
    bool isclone[N<<1];
    int sa[N<<1];
    int insert(int lst,int c){
        int cur=++tot,p=lst;
        len[cur]=len[p]+1,siz[cur]=1;
        for(;p>=0&&!ch[p][c];p=fai[p]) ch[p][c]=cur;
        if(p!=-1){
            int q=ch[p][c];
            if(len[p]+1==len[q]) fai[cur]=q;
            else{
                int clone=++tot;isclone[clone]=true;
                memcpy(ch[clone],ch[q],sizeof ch[q]);
                len[clone]=len[p]+1,fai[clone]=fai[q],pos[clone]=pos[q];
                for(;p>=0&&ch[p][c]==q;p=fai[p]) ch[p][c]=clone;
                fai[cur]=fai[q]=clone;
            }
        }
        return cur;
    }
    int mrk=-1,dfn[N<<1];
    void dfs(int u){
        if(!isclone[u]) sa[dfn[u]=++mrk]=pos[u];//这里放的就是原串的位置。
        sort(ifai[u].begin(),ifai[u].end(),cmp);
        for(node v:ifai[u]) dfs(v.id),siz[u]+=siz[v.id];
    }
    void build(){
        for(int i=1;i<=tot;i++) ifai[fai[i]].push_back(node{s[pos[i]-len[fai[i]]],i});
        dfs(0);
    }
}F;

因为根据鸽巢定律，在fail树中每一个节点的儿子不超过字符集大小个，所以在字符集为小写字母的时候，复杂度可以看作是O(n)的。

当然，你也可以用计数排序使得这个这个复杂度不受字符集大小的影响。简单来说，将所有节点按照它的字符a排序，然后按顺序push进它的父亲即可。

经测试，这种写法并不能通过洛谷的数据，原因是空间太大。 同时在LOJ上，时间并没有直接单log SA跑得快。

所以还是老实写SA吧……