2715. 后缀数组
2022/4/27 23:42:42
本文主要是介绍2715. 后缀数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
2715. 后缀数组
给定一个长度为 \(n\) 的字符串,只包含大小写英文字母和数字。
将字符串中的 \(n\) 个字符的位置编号按顺序设为 \(1∼n\)。
并将该字符串的 \(n\) 个非空后缀用其起始字符在字符串中的位置编号表示。
现在要对这 \(n\) 个非空后缀进行字典序排序,并给定两个数组 \(SA\) 和 \(Height\)。
排序完成后,用 \(SA[i]\) 来记录排名为 \(i\) 的非空后缀的编号,用 \(Height[i]\) 来记录排名为 \(i\) 的非空后缀与排名为 \(i−1\) 的非空后缀的最长公共前缀的长度(\(1≤i≤n\))。
特别的,规定 \(Height[1]=0\)。
请你求出这两个数组。
输入格式
共一行,包含一个长度为 \(n\) 的仅包含大小写英文字母或数字的字符串。
输出格式
第一行包含 \(n\) 个整数,表示 \(SA\) 数组。
第二行包含 \(n\) 个整数,表示 \(Height\) 数组。
数据范围
\(1≤n≤10^6\)
输入样例:
abababab
输出样例:
7 5 3 1 8 6 4 2 0 2 4 6 0 1 3 5
解题思路
后缀数组,倍增
后缀数组有两个关键的数组:
在后缀形成的数组 \(x[i]\) 中,
-
\(SA[i]\) 数组表示数组 \(x\) 中 排名为 \(i\) 的数组下标
-
\(Height[i]\) 表示 \(x[i]\) 和 \(x[i-1]\) 的最长公共前缀
\(\color{red}{如何倍增求解 SA 数组?}\)
基于基数排序的思想,设置一个桶 \(c[i]\) 表示值为 \(i\) 的数的数量,先将所有后缀子串按第一个字符排序,基数排序是稳定的,当第一个字符相等时不会改变原后缀子串的顺序,每次排序按长度排序,长度不足后面用字典序最小的字符补齐,例如前一次倍增拍好了长度为 \(k\) 的子串,此时排序长度为 \(2\times k\) 的子串,由于基数排序的稳定性,整体上可以将长度为 \(2\times k\) 的子串先将后 \(k\) 个字符排序,再将前 \(k\) 个字符排序,这样可以保证对于长度为 \(2\times k\) 的子串来说,前 \(k\) 个子串相等,后 \(k\) 个子串也会是排好序的,这样长度为 \(2\times k\) 的子串就排好了序,同时可求解 \(SA\) 数组
- 时间复杂度:\(O(nlogn)\)
\(\color{red}{如何求解 Height 数组?}\)
- 时间复杂度:\(O(n)\)
代码
这篇关于2715. 后缀数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南