社区讨论

突然想到的一个规避 SA 中 height 数组闭开区间分类讨论的方法

2020/09/17 10:29学术版参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

令

h_j

倍增，即定义新的数组

h'_j

使得：

查询时转化为区间

[2\text{rnk}_a + 1, 2\text{rnk}_b + 1]

的最小值。这里是闭合区间，可以省去一些麻烦的讨论。

数组长度由

n

变为

2n + 1

。

例如：

PLAIN

    1   2   3   4   5   6   7   8   9
h:  h1  h2  h3  h4
h': inf h1  inf h2  inf h3  inf h4  inf

查询排名为

2, 4

的后缀的

\text{lcp}

，则我们可以查询

(2, 4]

中的

\min\{h_i\}

；这相当于查询

[2 \times 2 + 1, 2 \times 4 + 1] = [5, 9]

中的

\min\{h'_i\}

。

共 4 条回复，欢迎继续交流。

正在加载回复...