前言
阅读此篇前，可先阅读后缀数组
LCP
LCP 就是最长公共前缀，在后缀数组中，(LCP(i,j)) 就代表从 (sa_i) 开始的后缀和从 (sa_j) 开始的后缀的最长公共前缀。
height 的定义
(height[i]=LCP(sa[i],sa[i-1]))，即从 (i) 开始的后缀与它前一个的后缀的最长公共前缀。
一些性质
(height[rak[i]] ge height[rak[i-1]]-1)
证明：
当 (height[rak[i-1]] le 1) 时，很好看出，(height[rak[i]] ge 0)，故正确。
当 (height[rak[i-1]] > 1) 时,因为 (LCP(i-1,sa[rak[i-1]-1])=height[rak[i-1]] > 1)，那么设这个最长公共为 (aA)（其中 (a) 代表一个字符 (A) 代表一个字符串），从 (i-1) 开始的后缀为 (aAB)，从 (sa[rak[i-1]-1]) 开始的后缀为 (aAC)，所以从 (i) 开始的后缀为 (AB)，从 (sa[rak[i-1]-1]+1) 开始的后缀就为 (AC)，所以 (LCP(i,sa[rak[i-1]-1]+1)=|A|)。设从 (sa[rak[i]-1]) 开始的后缀就为 (D)。
那么因为 (aAB > aAC)，所以 (AB>AC)，因为从 (sa[rak[i]-1]) 开始的后缀只比从 (i) 开始的后缀少一位，那么 (AB > D ge AC)，所以 (D) 肯定有一个 (A) 的前缀，即 (height[rak[i]] ge |A|)，(height[rak[i]] ge height[rak[i-1]]-1)
Code
void GetHeight(){
int k=0;
for(int i=1;i<=n;++i) {
if(k) k--;
while(s[i+k]==s[sa[rak[i]-1]+k]) ++k;
height[rak[i]]=k;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
