首页 > 题解 > luogu 3809 【模板】后缀排序

luogu 3809 【模板】后缀排序

题目背景

这是一道模板题。

题目描述

读入一个长度为 n 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。

输入输出格式

输入格式:

一行一个长度为 n n 的仅包含大小写英文字母或数字的字符串。

输出格式:

一行,共n个整数,表示答案。

输入输出样例

输入样例#1: 复制

ababa

输出样例#1: 复制

5 3 1 4 2

说明

n <= 10^6

题解

后缀自动机怎么后缀排序呢?加入节点的时候记录一下这个点是不是代表后缀。建完以后重建一下后缀树在上面dfs就可以了= =(注意重建的时候是字典序排序,不是拓扑序

这样的做法时间比较优越,是$O(n)$的。但是注意这里的字符集是62,长度是1e6,这样数组就开不下了。。(算了一下最后是544mb)

所以儿子的转移要硬套一层map。。没想到还能卡过去,最后时间4.7s


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×