gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-28 04:12:03 24 4
gpt4 key购买 nike

标题差不多。

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

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

最佳答案

其实很简单。后缀数组告诉您在对后缀树进行从左到右的深度优先遍历时遇到的后缀序列。 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

关于c++ - 如何从 LCP 数组和后缀数组构造后缀树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57502012/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com