后缀数组的height数组有什么性质
关注:40 答案:2 悬赏:19
解决时间 2024-04-16 21:44
- 已解决小废王
- 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个后缀的最长公共前缀的长度。
（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>