시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 29 | 13 | 12 | 54.545% |
A word $w$ is a lyndon word if and only if it is strictly smaller than all its proper suffixes. For example, aab
is a lyndon word, while aa
is not a lyndon word.
Chiaki has a string $s_1s_2\dots s_n$ of length $n$. She would like to know $l_i$, that is the length of the longest prefix of $s_i s_{i + 1} \dots s_{n}$ which is a lyndon word.
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \leq n \leq 10^5$). The second line contains a string $s_1 s_2 \dots s_n$ consists of lowercase characters.
The sum of all $n$ does not exceed $10^5$.
For each test case, output $n$ integers denoting $l_1, l_2, \dots, l_n$.
3 3 aaa 3 aab 3 cba
1 1 1 3 2 1 1 1 1