最长的通用前缀阵列

Question

以下是Suffix array和LCP array字符串信息MISSISSIPPI.我知道这LCP提供了有关str[i - 1]和之间最长公共前缀的长度的信息str[i].如何在此字符串的任意两个任意后缀之间获得最长的公共前缀长度.例如,我想要MISSISSIPPI和之间最长的公共前缀ISSIPPI

SA  LCP
12  0     $
11  0     I$
8   1     IPPI$
5   1     ISSIPPI$
2   4     ISSISSIPPI$
1   0     MISSISSIPPI$
10  0     PI$
9   1     PPI$
7   0     SIPPI$
4   2     SISSIPPI$
6   1     SSIPPI$
3   3     SSISSIPPI$

Answer 1

来自http://en.wikipedia.org/wiki/Suffix_array,我们知道"属于一组连续排序后缀的最小lcp值给出所有这些后缀中最长的公共前缀的事实也是有用的." 所以在你的情况下,MISSISSIPPI和ISSIPPI之间的LCP是min(4,0)= 0.

您可以通过http://en.wikipedia.org/wiki/Range_Minimum_Query找到时间范围O(1)中的最小值,如果您查看那里的TopCoder链接,有很多关于替代方法的信息.