用后缀数组构造后缀树

后缀树就是把所有后缀插入到trie之后,把只有一个分支的单链合并到一起,使得状态数减小至O(n)
下图为bananas的后缀树

定义边的长度为边上字符串的长度,点的深度为点到根的边权和。
容易发现,叶节点的DFS序就是按照叶节点对应的后缀字典序排列的,且相邻叶节点的LCA的深度为相邻两个后缀LCP的长度。
那么构造的时候就将后缀从大到小加入,同时使得这棵树满足上述性质即可。代码一看就懂了。

int n;
std::vector<int> sa,rank,height;

struct Edge {
    int to,v;
};

std::vector<Edge> G[XN];
int root,pcnt,last,dis[XN],fa[XN],size[XN];

int NewNode() {
    G[++pcnt].clear();
    size[pcnt]=fa[pcnt]=dis[pcnt]=0;
    return pcnt;
}

void AddEdge(int x,int y,int v) {
    G[x].push_back({y,v});
    dis[y]=dis[fa[y]=x]+v;
}

void Build() {
    pcnt=0;
    root=NewNode();
    AddEdge(root,last=NewNode(),n-sa[1]+1);
    size[last]=1;
    for(int i=2;i<=n;++i) {
        int p=last,np=NewNode();
        while(dis[p]>height[i])
            p=fa[p];
        if(dis[p]!=height[i]) {
            int d=height[i]-dis[p],o=NewNode();
            auto e=G[p].back();
            G[p].pop_back();
            AddEdge(p,o,d);
            AddEdge(o,e.to,e.v-d);
            p=o;
        }
        AddEdge(p,np,n-sa[i]+1-height[i]);
        size[last=np]=1;
    } 
}

参考https://blog.csdn.net/u011542204/article/details/51231962

发表评论

电子邮件地址不会被公开。 必填项已用*标注