苏州网站建设比较好的公司,二维码生成器app下载,wordpress只显示置顶文章,婚恋网站排名前三高度数组
1.理解相关数组的含义 rk[i]#xff1a;表示原始下标为i的后缀字符串排序后对应的下标#xff08;也就是原始下标为i的后缀字符串排序后为第rk[i]小#xff09; height[i]#xff1a;表示排名为i和i-1的后缀字符串的最长公共前缀的长度#xff0c;注意这里的i是…高度数组
1.理解相关数组的含义 rk[i]表示原始下标为i的后缀字符串排序后对应的下标也就是原始下标为i的后缀字符串排序后为第rk[i]小 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)sAheight[rk[i-1]]。
则原始下标i对应的后缀字符串为AB目前已知有后缀字符串AC的字典序比AB小而lca(AB,AC)Aheight[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可以看作上面的sbc可以看作上面的Aedc可以看作上面的Babcedc可以看作上面的C。那么lca(abcabcedc,abcedc)abc3height[rk[i-1]]。
则原始下标i对应的后缀字符串为bcedc目前已知有后缀字符串bcabcedc的字典序比bcedc小而lca(bcedc,bcabcedc)bc2height[rk[i-1]]-1。但是按字典序排序后排在rk[i]-1位的后缀字符串为不一定为bcabcedc。如果存在一个字符串按照字典序排序后插在bcedc和bcabcedc之间至少该字符串一定包含bc。如字符串是bcbabcabcedc按照字典序他应该在bcedc和bcabcedc之间此时lca(bcedc,bceabcabcedc)3height[rk[i-1]]-1至此定理得证。
建议边读边自己在本子上写帮助理解。
3.模板代码
private static void get_height() {// TODO Auto-generated method stubfor(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(ki n j k n s[ki] s[kj]) k;height[rk[i]]k;}
}rk数组和sa数组互为逆所以可以通过sa数组快速得到rk数组rk[sa[i]] i 字典序排名为i的字符串不需要求高度数组if(rk[i] 1) continue; k记录的是上一个后缀数组的高度数组大小根据定理当前从k-1开始找即可所以有if(k ! 0) k--;
