后缀数组(后续)

后缀数组 Height

利用后缀数组快速求出2个后缀的lcp长度
lcp:最长公共前缀
lcp(suf(i),suf(j))
记Height[l] = 排名第(l-1)后缀和排名第l后缀的lcp长度
Height[l] = lcp(suf(SA[l-1]),suf(SA[l]))

l = 后缀suf(i)的排名
r = 后缀suf(j)的排名
结论:

两个子串最长公共前缀

lcp(suf(i),suf(j)) = min(Height[l+1]…Height[r] )
即两个后缀的lcp = 它们排名区间中Height的最小值
维护rmq

求Height数组

全部评论

相关推荐

点赞 评论 收藏
分享
Tom哥981:这份简历是“大一新生硬凹资深后端”的典型反面教材,槽点离谱到能让面试官直接笑出声: ### 1. 「年龄+入学时间」和项目复杂度完全脱节,可信度直接归0 你2024年7月才入学(现在刚读了1年多),19岁的大一新生,能把Vue3+Spring Boot+ShardingSphere+K8s+AI这些技术全塞进两个项目里?别说实际开发,光把这些技术的文档看完都得半年——这不是“能力强”,是“把招聘JD里的技术词全抄过来造假”,明摆着没碰过实际代码
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务