【后缀数组之height数组】

模板奉上

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++) //求h[i] = height[rank[i]];
      ;
return;
}

概念:

(1)height 数组:定义height[i]=suffix(SA[i-1])和suffix(SA[i])的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀的长度 。

(2)h[i]=height[rank[i]],也就是suffix(i)和排序后在它前一名的后缀的最长公共前缀的长度。

(3)函数lcp(u,v)=max{i|u=v},也就是从头开始顺次比较u和v的对应字符,对应字符持续相等的最大位置,称为这两个字符串u,v的最长公共前缀的长度。

(4)LCP(i,j):对正整数i,j 定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]),其中i,j 均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。

性质

(1)LCP(i,j)=min{height[k]|i+1≤k≤j},也就是说,计算LCP(i,j)等同于询问一维数组height[] 中下标在i+1 到j 范围内的所有元素的最小值。

(2)对于i>1 且Rank[i]>1,一定有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[1],h[2],……,h[n]的顺序计算,并利用h 数组的性质,时间复杂度可以降为O(n)。

  即:

   rank[i-1] = q-1 suffix(k):        rabaa

   rank[i-1] = q    suffix(i-1):    racadabrabaa         h[i-1] = 2;

   ......

   rank[k-1] = p-1   suffix(k-1):     abaa

   rank[i] = p          suffix(i):       acadabrabaa         h[i] = 1 (h[i] >= h[i-1]-1 = 1;)

 

计算数组h[]

可以令i从1循环到n(此循环中i的意义为suffix(i))按照如下方法依次算出h[i]:

  若 Rank[i]=1,则h[i]=0。字符比较次数为0。

  若i=1或者h[i-1]≤1,则直接将Suffix(i)和Suffix(Rank[i]-1)从第一个字符开始依次比较直到有字符不相同,由此计算出h[i]。字符比较次数为h[i]+1,不超过h[i]-h[i-1]+2。

  否则,说明i>1,Rank[i]>1,h[i-1]>1,根据性质2,Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1 个字符是相同的,于是字符比较可以从h[i-1]开始,直到某个字符不相同,由此计算出h[i]。字符比较次数为h[i]-h[i-1]+2。

  可求得最后算法复杂度为O(n)。

上一篇:Android自定义之TextView跑马灯的监听


下一篇:移动APP服务端API设计应该考虑到的问题