我在看后缀数组，它用来计算两个后缀的最长公共前缀。
消息人士说：
“两个后缀之间的lcp是数组中所有相邻后缀对中lcp的最小值”
即lcp(x,y)=min{ lcp(x,x+1),lcp(x+1,x+2),.....,lcp(y-1,y) }
其中x和y是字符串的两个索引，字符串的两个后缀从这里开始。
我不相信string"abca"示例中的语句。lcp(1,4)=1（考虑基于1的索引）
但是如果我应用上面的公式lcp(1,4)=min{lcp(1,2),lcp(2,3),lcp(3,4)}
我认为lcp(1,2)=0。
所以根据这个方程，答案必须是0。
我是不是在哪里弄错了？
最佳答案
我认为源引用的索引不是字符串本身的索引，而是排序后缀的索引。
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
关于string - 最长公共(public)前缀属性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16128400/