#60. Lyndon 分解

Lyndon 分解

当前没有测试数据。

题目描述

这是一道模板题。

读入一个由大小写英文字母或数字组成的字符串 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
2 4 5
bbababaabaaabaaaab
1 2 4 6 9 13 18
azAZ0129
2 4 8

数据范围与提示

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