后缀数组学习笔记 ----height引理的证明

(lcp(i,j)) 表示 后缀 (i) 和后缀 (j) 的最长公共前缀的长度

(height[i] = lcp(sa[i],sa[i-1])) 表示第 (i) 名的后缀与它前一名的后缀的最长公共长度

(height[1] = 0)

引理：(heigh[rk[i]]>=height[rk[i-1]]-1)

证明如下：

当： (height[rk[i-1]]<=1) 时，上式子显然成立

当：(height[rk[i-1]]>1) 时：

• 设后缀 (i-1) 为 (aAD) （(A) 是一个长度为 (height[rk[i-1]]-1) 的字符串），那么后缀 (i) 为 (AD)
• 设后缀 (sa[rk[i-1]-1]) 为 (aAB) ((B)<(D)) ，那么(height[rk[i-1]] = lcp(i-1,sa[rk[i-1]-1]) = aA) 。
• 因为 (sa[rk[i-1]-1]+1 = AB) ，而后缀 (i) 是 (AD) ，所以 (sa[rk[i-1]-1]+1) 一定在 (i) 的前面。
• 设 (r = rk[i],l = rk[sa[rk[i-1]-1]+1]) ，那么 (l<=rk[i]-1<r) ，因为 (l,r) 都含有 (A)，所以 (rk[i]-1) 一定含有 (A)， 所以 (rk[i]-1 = A[C|D])
• 所以 (lcp(i,sa[rk[i]-1]):AX) (X) 可能为空

//求height数组，因为k最多减n次，最多加2*n次，所以复杂度是 O(n)
for(int i=1,k=0;i<=n;i++){
    if(k) k--;
    while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
    height[rk[i]] = k;
}