计算后缀数组的Height数组
定义height[i]为suffix(sa[i-1])和suffix(sa[i])的最长公共前缀.对于j和k,假设rank[j] < rank[k],则:
suffix(j)和suffix(k)的最长公共前缀为height[rank[j]+1],height[rank[j]+2],height[rank[j]+3],...,height[rank[k]]中的最小值.
今天的要记录的是:如何快速地求出height数组的值.
h数组
为了高效地求出height数组,引入h数组的定义:
h[i]=height[rank[i]],即h[i]为suffix(i)和排名在它前一名的后缀的最长公共前缀.
那么h数组有一个重要的性质:
h[i]>=h[i-1]-1
证明如下:
假设suffix(k)是排在suffix(i-1)前一名的后缀,那么根据h数组的定义,他们的最长公共前缀为h[i-1].如果:
①h[i-1]<=1,那么h[i]>=1-1=0成立.
②h[i-1]=1,那么表示suffix(k)和suffix(i-1)有至少有两个公共前缀字符.因此suffix(k+1)必定排在suffix(i)的前面.而且他们的公共前缀为h[i-1]-1.也就是h[i-1]-1是height[rank[k+1]+1],height[rank[k+1]+2],...height[rank[i]]之间的最小值,所以suffix(i)和在它前一名的后缀的最长后缀至少为h[i-1]-1.
代码实现
因为rank数组和SA数组互逆,因此由h[i]=height[rank[i]]可以得到height[i]=h[SA[i]].不用保存h数组就可以算出height数组:
void CalHeight(int *SA,int *height,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++)
rank[sa[i]=i;
for(i=0;i<n;i++)
{
if(k!=0)
k=k-1;
else
k=0;
j=sa[rank[i]-1]; //suffix(j)排在suffix(i)前一名
while(r[i+k]==r[j+k])
k++;
height[rank[i]]=k;
}
}
精简的代码
void CalHeight(int *source,int *SA,int *rank,int *height,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[SA[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=SA[rank[i]-1];source[i+k]==source[j+k];k++);
return;
}