后缀数组的一些性质----height数组

时间:2023-03-08 17:28:08
后缀数组的一些性质----height数组

  height数组:定义 height[i] = suffix[i-1] 和 suffix[i] 的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。那么对于 j 和 k 不妨设 Rank[j] < Rank[k] ,则有以下性质:

  suffix[j] 和 suffix[k] 的最长公共前缀为 height[Rank[j]+1] , height[Rank[j]+2],......,height[Rank[k]] 中的最小值。

  例如,字符串为“aabaaaab”,求后缀“abaaaab”和后缀“aaab”的最长公共前缀,如图4所示:

  后缀数组的一些性质----height数组

  那么应该如何高效的求出height值呢?

  定义 h[i] = height[Rank[i]],也就是suffix(i)和它前一名的最长公共前缀。

  h数组有以下性质:h[i]>=h[i-1]-1.

  证明:

  设suffix[k]是排在suffix[i-1]前一名的后缀,则它们的最长公共前缀是h[i-1]。那么suffix[k+1]将排在suffix[i]前面(这里要求h[i-1]>1,如果h[i-1]<=1原式显然成立)并且suffix[k+1]和suffix[i]的最长公共前缀是h[i-1]-1,所以suffix(i)和它前一位的最长公共前缀至少是h[i-1]-1。

  实现的时候没必要保存h数组,只需按照h[1],h[2],h[3],...,h[n]的顺序计算即可。

  代码:

 

int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
int i,j,k=;
for(i=;i<=n;i++) rank[sa[i]]=i;
for(i=;i<n;height[rank[i++]]=k)
for(k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k];k++);
return;
}