同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1601_Lyndon分解

2022-5-16 18:17| 发布者: Hocassian| 查看: 52| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950417250199-Problem List-采集的数据-后羿采集器.html

Pro.ID

1601

Title

Lyndon 分解

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1601

AC

0

Submit

0

Ratio

-

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

这是一道模板题。

读入一个由大小写英文字母或数字组成的字符串 s ，请把这个字符串分成若干部分 s=s₁s₂s₃…s_m，使得每个 s_i 都是 Lyndon Word，且 ∀ 1 ≤ i < n : s_i ≥ s_i+1 。输出 s₁ 到 s_m 这些串长度的右端点的位置。位置编号为 1 到 n。

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

输入

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

1 ≤∣s∣≤ 2²⁰

输出

Description

这是一道模板题。

读入一个由大小写英文字母或数字组成的字符串 s ，请把这个字符串分成若干部分 s=s₁s₂s₃…s_m，使得每个 s_i 都是 Lyndon Word，且 ∀ 1 ≤ i < n : s_i ≥ s_i+1 。输出 s₁ 到 s_m 这些串长度的右端点的位置。位置编号为 1 到 n。

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

Input

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

1 ≤∣s∣≤ 2²⁰

Output

一行若干个整数，第 i 个表示 s_i 的右端点在 s 中的位置。

Sample Input

Sample #1
ababa

Sample #2
bbababaabaaabaaaab

Sample #3
azAZ0129

Sample Output

Sample #1
2 4 5

Sample #2
1 2 4 6 9 13 18

Sample #3
2 4 8

样例输入

Sample #1
ababa

Sample #2
bbababaabaaabaaaab

Sample #3
azAZ0129

样例输出

Sample #1
2 4 5

Sample #2
1 2 4 6 9 13 18

Sample #3
2 4 8

提示

作者

最新评论

相关分类

返回顶部