string - 最长公共(public)前缀属性

Question

我正在研究后缀数组及其用于计算两个后缀的最长公共(public)前缀的用途。

来源说:

"The lcp between two suffixes is the minimum of the lcp's of all pairs of adjacent suffixes between them on the array"

即lcp(x,y)=min{ lcp(x,x+1),lcp(x+1,x+2),.....,lcp(y-1,y) }其中 x 和 y 是字符串的两个索引，字符串的两个后缀从此处开始。

我不相信字符串 "abca" 示例中的声明。

lcp(1,4)=1(考虑基于 1 的索引)

但是如果我应用上面的等式那么

lcp(1,4)=min{lcp(1,2),lcp(2,3),lcp(3,4)}

我认为 lcp(1,2)=0。

所以根据等式，答案必须是0。

我是不是哪里弄错了？

Answer 1

我认为源引用的索引不是字符串本身的索引，而是排序后缀的索引。

a
abca
bca
ca

因此

lcp(1,2) = lcp(a, abca) = 1
lcp(1,4) = min(lcp(1,2), lcp(2,3), lcp(3,4)) = 0