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. 后缀数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程