#129. Lyndon 分解

内存限制:233 MiB 时间限制:233 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EtaoinWu

题目描述

这是一道模板题。

读入一个由大小写英文字母或数字组成的字符串 ss ,请把这个字符串分成若干部分 s=s1s2s3sms=s_1s_2s_3\dots s_m,使得每个 sis_i 都是 Lyndon Word,且 1i<n:sisi+1\forall 1\leq i <n:s_i \geq s_{i+1}。输出 s1s_1sms_m 这些串长度的右端点的位置。位置编号为 11nn

一个字符串 ss 是一个 Lyndon Word 表示 ss 是其所有后缀中的最小者。

输入格式

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

输出格式

一行若干个整数,第 ii 个表示 sis_i 的右端点在 ss 中的位置。

样例

样例输入1

ababa

样例输出1

2 4 5

样例输入2

bbababaabaaabaaaab

样例输出2

1 2 4 6 9 13 18

样例输入3

azAZ0129

样例输出3

2 4 8

数据范围与提示

1s2201 \leq |s|\leq 2^{20}