通用废塑料
后缀数组的height数组有什么性质
关注:1  答案:2  悬赏:19
解决时间 2022-06-28 14:38
  • 已解决
  • 2022-05-13 19:06
最佳答案
  • £陌予★倾城╮
  • 2022-04-23 21:07
(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楼Cytheria
  • 2022-04-23 21:07
在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。可以说,在信息学竞赛中后缀数组比后缀树要更为实用。    具体应用可以参考  <a href="http://wenwen.soso.com/z/urlalertpage.e?sp=shttp%3a%2f%2fbaike.baidu.com%2fview%2f1240197.htm" target="_blank">http://baike.baidu.com/view/1240197.htm</a>