c++ - 如何从 LCP 数组和后缀数组构造后缀树

Question

标题差不多。

我使用 DC3 算法在 O(n) 时间内创建了一个后缀数组。然后，我在 O(n) 时间内使用 Kasai 算法创建了一个 LCP 数组。现在我需要从我拥有的两个数组创建一个后缀树。如何做到这一点？ 我查看了期刊论文并使用 Google 环顾四周，但找不到方法。

我看到一个 coursera 视频描述了这个过程，但他们没有说明他们使用的是什么方法，我怀疑它是线性时间算法。

Answer 1

其实很简单。后缀数组告诉您在对后缀树进行从左到右的深度优先遍历时遇到的后缀序列。 LCP 数组告诉您在开始对应于下一个后缀的新边之前需要向上走多远。假设字符串 s 的末尾有一些独特的字符(因此每个后缀都由一个叶节点表示)，该算法看起来大致如下:

let root = new node
let p = new node
make p a child of root with edge label S[0] (the least suffix)
for (int i = 1; i < s.size(); i++) {
    let l = LCP[i-1] (the LCP length of S[i] and S[i-1])
    let prevP = null
    while ((depth of p) > l) {
        // note that "depth" means total edge length from root to p, not
        // total number of edges from root to p
        prevP := p
        p := (parent of p)
    }
    if ((depth of p) == l) {
        let q = new node
        make q a child of p, with edge label S[i][l...]
        p := q
    } else {
        // we need to "split" the edge from p to prevP
        let q = new node
        let prevDepth = depth of prevP
        unlink prevP from p
        make q a child of p, with edge label S[i-1][(depth of p)...(l - 1)]
        make prevP a child of q, with edge label S[i-1][l...(prevDepth - 1)]
        let r = new node
        make r a child of q, with edge label S[i][l...]
        p := r
    }
}
return root