后缀数组模板之高度数组

2023-12-15 19:32:19

高度数组

1.理解相关数组的含义

  1. rk[i]:表示原始下标为i的后缀字符串排序后对应的下标(也就是原始下标为i的后缀字符串排序后为第rk[i]小)

  2. height[i]:表示排名为i和i-1的后缀字符串的最长公共前缀的长度,注意这里的i是排名,不是原始下标

2.定理证明

定理:height[rk[i]]>=height[rk[i-1]]-1

采用先抽象后具体的方式进行详细的证明。

抽象证明

假设原始下标i-1对应的后缀字符串为sAB,则按字典序排序后排在rk[i-1]-1位的后缀字符串为sAC。注意这里的s表示某个字符,A、B和C表示某些字符。那么lca(sAB,sAC)=sA=height[rk[i-1]]。

则原始下标i对应的后缀字符串为AB,目前已知有后缀字符串AC的字典序比AB小,而lca(AB,AC)=A=height[rk[i-1]]-1,则按字典序排序后排在rk[i]-1位的后缀字符串为不一定为AC,但是如果存在一个字符串按照字典序排序后插在AB和AC之间,至少该字符串一定包含A,假设该字符串是AD,那么在D里面可能存在某些字符与B里的字符相等,因此lca(AB,AD)>=height[rk[i-1]]-1,至此定理得证。

实例证明

假设原始下标i-1对应的后缀字符串为abcedc,则按字典序排序后排在rk[i-1]-1位的后缀字符串为abcabcedc。此时我们用的是具体的字符串,不再是抽象表示,这里的a可以看作上面的s,bc可以看作上面的A,edc可以看作上面的B,abcedc可以看作上面的C。那么lca(abcabcedc,abcedc)=abc=3=height[rk[i-1]]。

则原始下标i对应的后缀字符串为bcedc,目前已知有后缀字符串bcabcedc的字典序比bcedc小,而lca(bcedc,bcabcedc)=bc=2=height[rk[i-1]]-1。但是按字典序排序后排在rk[i]-1位的后缀字符串为不一定为bcabcedc。如果存在一个字符串按照字典序排序后插在bcedc和bcabcedc之间,至少该字符串一定包含bc。如字符串是bcbabcabcedc,按照字典序他应该在bcedc和bcabcedc之间,此时lca(bcedc,bceabcabcedc)=3>height[rk[i-1]]-1,至此定理得证。

建议边读边自己在本子上写,帮助理解。

3.模板代码

private static void get_height() {
	// TODO Auto-generated method stub
	for(int i = 1;i <= n;i++) rk[sa[i]] = i;
	for(int i = 1,k = 0;i <= n;i++) {
		if(rk[i] == 1) continue;
		if(k != 0) k--;
		int j = sa[rk[i]-1];
		while(k+i <= n && j + k <= n && s[k+i] == s[k+j]) k++;
		height[rk[i]]=k;
	}
}
  1. rk数组和sa数组互为逆,所以可以通过sa数组快速得到rk数组rk[sa[i]] = i

  2. 字典序排名为i的字符串不需要求高度数组if(rk[i] == 1) continue;

  3. k记录的是上一个后缀数组的高度数组大小,根据定理当前从k-1开始找即可,所以有if(k != 0) k--;

文章来源:https://blog.csdn.net/qq_53237241/article/details/135023422
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。