LCP的引入笔记

——《高级数据结构》
前面介绍了几种算法构造后缀数组，虽然得到的后缀数组已经能处理一些简单的问题，但是为了让其能够具有与后缀树相媲美的字符串处理能力，需要引入辅助工具——LCP（Longest Common Prefix,最长公共前缀）。
对于字符串St1和St2,它们的最长公共前缀LCP_Str(St1,St2)定义为最大的整数len，满足St1的len次方=St2的len次方（记号意义同前文中）。当然，len不会超过两者中较短字符串的长度。对于后缀数组，我们需要知道的是任意两个后缀的最长公共前缀。因此定义LCP_Idx(i,j)=LCP_Str(Suffix(SA(i)),Suffix(SA(j))),即排名第i的后缀和排名为j的后缀的LCP。
不难发现，LCP_Idx与操作元顺序无关，并且对于两个相同的字符串，它们的LCP即它们的长度，因此为了求解方便，我们只需要求所有i<j的LCP_Idx(i,j).
如果用朴素的方法计算LCP，那么将会非常低效。由于是针对后缀计算LCP，借鉴倍增算法的思想，在这里需要利用题目的特殊性。以下给出一种线性时间复杂度的算法。
我们首先给出需要利用到的结论，其证明将在之后给出。
（1）对于i<j，LCP_idx(i,j)=min(LCP_Idx(k-1,k)|i+1<=k<=j)
(2)对于数组height，其中height[i]=LCP_Idx(i-1,i),对于i=0的边界情况，令height[0]=0。有了height数组，对于任意两个后缀SA(i)和SA（j）,根据结论（1），只需要计算min{LCP_Idx(k-1,k)|i+1<=k<=j}。由于对于固定的后缀数组，其height数组也是固定的，因此该问题即经典的RMQ问题。通过对height数组进行RMQ的预处理，便可以在O（1）的时间内回答每一对后缀的LCP了。
（3）为了计算height数组，我们同样需要如下的结论；对于i>0且Rank(i)>0，有height[Rank(i)]>=height[Rank(i-1)]-1。据此按照i递增的顺序求解height[Rank(i)]。计算height[Rank(i)]时，不要从第一个字符开始比较，而是从第height[Rank(i-1)]个字符开始比较。
用步骤3的方法可以在O(n)的时间内得到height数组，至此可以完美解决本问题。
根据以上描述，不难得到如下的代码（仅构造height数组，RMQ过程省略）：
//参数分别为：字符串st（下标从0开始），后缀数组指针，名次数组指针，待计算的height数组指针及字符串长度
void GetHeght(int* st,int* SA,int* rank,in* height,int n)
{
int L=0;
for (int i=0;i<n;++i)
if (rank[i]>0)
{
int j=SA[rank[i]-1];
while ((i+L<n)&&(j+L<n)&&(st[i+L]==st[j+L]))
L++;
height[rank[i]]=L;
if (L>0) L–;
}
}

下面给出以上相关的证明
1.对于i<j,LCP_Idx(i,j)=min(LCP_Idx(k-1,k)|i+1<=k<=j)
证明：步骤一：对任意0<=i<j<k<n;有LCP_Idx(i,k)=min(LCP_Idx(i,j),LCP_Idx(j,k))。假设len=min{LCP_Idx(i,j),LCP_Idx(j,k)},那么有Suffix(SA(i))的len次方=Suffix（SA（j））的len次方=Suffix（SA（k））的len次方，因此Suffix（SA（i））的len次方=Suffix（SA（j））的len次方，即LCP_Idx(i,k)>=len;同时，若有LCP_Idx(i,k)>len；假设为len2，那么Suffix(SA(i))的len2次方=Suffix(SA(k))的len2次方。由i<j<k可知，Suffix（SA（i））的len2次方<=Suffix(SA(j)的len2次方)<=Suffix(SA(k))的len2次方，可得min{LCP_Idx(i,j),LCP_Idx(j,k)}>=len2,矛盾，所以LCP_Idx(i,k)<=len。得证。
步骤二：应用步骤一的结论将LCP_Idx(i,j)展开。若i+1=j，那么显然成立；否则，答案为min(LCP_Idx(i,i+1)),LCP_Idx(i,i+1)，LCP_Idx(i+1,j),第一项可以直接写出，第二项继续展开，最后的结果便是证明的式子。
2.对于i>0且Rank(i)>0,有height[Rank(i)]>=height[Rank(i-1)]-1
证明：当height[Rank(i-1)]<=1时显然成立，当height[Rank(i-1)]>1时，因为height[0]=0，所以Rank(i-1)>0。不妨令j=i-1，k=SA[Rank(j)-1],那么有height[Rank(i-1)]=LCP_str(Suffix(k),Suffix(j))>1。将这两个后缀各自去掉其第一个字符得到新的两个后缀为Suffix（k+1）和Suffix(j+1=i),显然LCP_Str(Suffix(k+1),Suffix(i))=LCP_Str(Suffix(k),Suffix(j))-1=height[Rank[i-1]]-1。同时，我们注意到，Suffix(k)<Suffix(j),去掉各自首字母得到的后缀仍然满足“小于”关系，即Suffix(k+1)<Suffix(j+1=i)，即Rank(k+1)<Rank(i)。根据证明1中的结论，由于Rank(i)-1>=Rank(k+1),故LCP_Idx(Rank(i)-1,Rank(i))>=LCP_Idx(Rank(k+1),Rank(i)).该不等式左边即为height[Rank(i)]，而右边为height[Rank(i-1)]=-1,故得证。
3。计算height数组过程的时间复杂度为 O(n)
证明：根据2中的结论，我们可以按照i从小到大的顺序计算height数组。计算height[Rank(i)]时，对于i>.0且Rank(i)>0的情况，我们从height[Rank(i-1)]-1开始，逐一比较，该过程总时间复杂度为O(n),好比蜗牛爬杆，每天至多爬到顶，每天下降一步，最后上爬的步数至多为2n；而对于i=0或者Rank(i)=0的情况，即使从头开始顺次比较，最坏也只要各自比较n次。综上所述，总共比较的次数不会超过4n次，故算法的时间复杂度为O（n）。