9038: [yosupo] String - Lyndon Factorization
[Creator : ]
Description
For a string $X = X _ 0 X _ 1 X _ 2 \cdots $ , we denote its substring $X _ a X _ {a+1} \cdots X _ {b-1}$ as $X[a,b)$ .
Given a string $S = S _ 0 S _ 1 S _ 2 \cdots S _ {N-1}$ of length $N$ . Find an array of integers $0 = a _ 0 \lt a _ 1 \lt a _ 2 \lt \ldots \lt a _ k = N$ so that $S[a _ 0 , a _ 1) , S[a _ 1 , a _ 2) , \ldots , S[a _ {k-1} , a _ k)$ is the Lyndon Factorization of $S$ .
Given a string $S = S _ 0 S _ 1 S _ 2 \cdots S _ {N-1}$ of length $N$ . Find an array of integers $0 = a _ 0 \lt a _ 1 \lt a _ 2 \lt \ldots \lt a _ k = N$ so that $S[a _ 0 , a _ 1) , S[a _ 1 , a _ 2) , \ldots , S[a _ {k-1} , a _ k)$ is the Lyndon Factorization of $S$ .
Input
$S$
Output
$a _ 0$ $a _ 1$ $a _ 2$ $\cdots$ $a _ k$
Constraints
$1 \leq N \leq 5\times 10^5$
Each character of $S$ is a lowercase English letter.
Each character of $S$ is a lowercase English letter.
Sample 1 Input
babaabaab
Sample 1 Output
0 1 3 6 9
Sample 2 Input
ababacaca
Sample 2 Output
0 8 9