最长常用前缀(Longest Common Prefixes)

假设我构建了一个后缀阵列，即整数给人以字典顺序字符串的所有后缀的起始位置的数组。

例如：对于一个字符串str=abcabbca ，

后缀数组是：

suffixArray[] = [7 3 0 4 5 1 6 2]

说明：

i   Suffix      LCP of str and str[i..]   Length of LCP
7   a           a                           1
3   abbca       ab                          2
0   abcabbca    abcabbca                    8
4   bbca        empty string                0
5   bca         empty string                0
1   bcabbca     empty string                0
6   ca          empty string                0
2   cabbca      empty string                0

现在有了这个suffixArray构造，我想找到的最长共同的前缀（LCP）的长度 str （字符串本身）和其他各个后缀 。什么是最有效的方式做到这一点？

基于您的评论，我认为我们有机会获得后缀数组SA以及标准的LCP阵列，即数据结构，它告诉我们，在索引i> 0，什么后缀的最长公共前缀的长度SA[i]和它的词典前身SA[i-1]是。

我会用字母L是指我们要构建的特殊的LCP阵列，如问题描述。我会用字母N指输入字符串的长度str 。

那么我们可以做到这一点：

确定的位置str后缀数组中。我们可以通过筛选做到这一点SA线性找到入口0 。（说明： str是后缀str开始位置0。因此， 0必须作为后缀阵列的条目）。
假设我们发现该条目是在索引k。然后，我们可以设置L[k]:=N ，我们因为SA[k]是字符串本身，并且具有共同的N个字符与自身的前缀。
然后，我们可以设置L[k-1]:=LCP[k]和L[k+1]:=LCP[k+1]因为这是标准的LCP是如何定义的。
然后，我们倒退从我：= K-2下降到0，并设置
```
 L[i] := min(LCP[i+1],L[i+1]) 
```
这样做是因为，在每次迭代i， LCP[i+1]告诉我们相邻后缀的最长公共前缀SA[i]和SA[i+1]和L[i+1]告诉我们最长的公共前缀先前处理的后缀的SA[i+1]和输入字符串str 。 L[i]必须是这两个最小，因为L[i]表示多久前缀SA[i]具有在共同与str ，并且不能比它在常见的前缀较长SA[i+1] ，否则其后缀数组中的位置将是更接近至k。
我们还从i计数正向：= K + 2到N，并设置
```
 L[i] := min(LCP[i],L[i-1]) 
```
基于同样的道理。