Дай мне услышать твой голос, расскажи мне истории о своём путешествии —
И о радости, и о боли, и о встречах, навсегда запечатлевшихся в сердце.
Условие задачи
Дана строка $S$ длины $n$, символы которой нумеруются с $1$. Обозначим через $S(i, j)=S_iS_{i+1}\cdots S_j$ подстроку строки $S$ с $i$-го по $j$-й символ включительно.
Если непустая строка $B$ одновременно является префиксом и суффиксом строки $X$ и $|B|<|X|$, то $B$ называется границей строки $X$, где $|X|$ обозначает длину строки $X$.
Изначально вы находитесь в подстроке $S(1, n)$. Каждый прыжок выполняется следующим образом:
- Выберите подстроку $X$ текущей подстроки.
- Выберите границу $B$ строки $X$, удовлетворяющую условию $2|B|\ge |X|$.
- Перейдите в подстроку, соответствующую вхождению $B$ в $X$ в качестве префикса или суффикса, выбрав любое из этих двух вхождений.
Например, если $S$ равна aabaaba и вы находитесь в $S(1, 7)$, можно выбрать $X=S(2, 7)=$ abaaba. Длина её границы aba равна ровно половине $|X|$, поэтому можно перейти в $S(2, 4)$ или $S(5, 7)$.
Для каждого $1\le i\le n$ найдите максимальное количество прыжков, которое можно совершить, начав в $S(1, n)$ и закончив в $S(i, i)$. Если добраться до этой подстроки невозможно, ответ равен $-1$. Разрешается не совершать ни одного прыжка.
Входные данные содержат несколько тестов.
Входные данные
Первая строка содержит целое число $T$ — количество тестов.
Далее последовательно задаются тесты. Каждый тест занимает одну строку, содержащую строку $S$.
Выходные данные
Для каждого теста выведите одну строку, содержащую $n$ целых чисел. $i$-е число должно быть ответом для $S(i, i)$ (если добраться до $S(i, i)$ невозможно, выведите -1).
Примеры
Входные данные 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Выходные данные 1
-1 2 2 -1 -1 -1 2 2 -1 -1 3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1 -1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1
Примечание
В первом тесте $S=$ abbababbab, а её префикс и суффикс длины $5$ оба равны abbab. Можно совершить два прыжка следующим образом:
- Сначала перейти в $S(1, 5)$, затем выбрать $S(2, 3)=$ bb и перейти в $S(2, 2)$ или $S(3, 3)$.
- Сначала перейти в $S(6, 10)$, затем выбрать $S(7, 8)=$ bb и перейти в $S(7, 7)$ или $S(8, 8)$.
Продолжить прыжки можно только в том случае, если первый прыжок привёл в одно из двух указанных вхождений abbab. При этом следующий прыжок может привести только в отдельный символ, поэтому максимальное количество прыжков для каждой из этих четырёх позиций равно $2$.
До остальных позиций добраться прыжками невозможно, поэтому ответ для них равен $-1$.
Примеры 2
См. файлы wind2.in и wind2.ans во вложениях. Этот пример удовлетворяет ограничениям подзадачи 3.
Примеры 3
См. файлы wind3.in и wind3.ans во вложениях. Этот пример удовлетворяет ограничениям подзадачи 5.
Примеры 4
См. файлы wind4.in и wind4.ans во вложениях. Этот пример удовлетворяет ограничениям подзадачи 6.
Примеры 5
См. файлы wind5.in и wind5.ans во вложениях. Этот пример удовлетворяет ограничениям подзадачи 8.
Ограничения
В этой задаче используются соответствующие зависимости между подзадачами.
| Подзадача | $n\le$ | $\sum n\le$ | Специальное свойство | Баллы |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Нет | $5$ |
| $2$ | $500$ | $14$ | ||
| $3$ | $5\times 10^3$ | $5\times 10^3$ | $21$ | |
| $4$ | $10^5$ | $10^5$ | $18$ | |
| $5$ | $2\times 10^5$ | $2\times 10^5$ | A | $15$ |
| $6$ | B | $13$ | ||
| $7$ | C | $2$ | ||
| $8$ | Нет | $12$ |
Специальное свойство A: существует непустая строка $P$, такая что $S$ является префиксом бесконечной периодической строки $P^{\infty}$ и $|P|\le 10$.
Специальное свойство B: строка $S$ сгенерирована случайным образом, то есть каждый символ $S$ выбирается равновероятно из алфавита размера $\ge 2$.
Специальное свойство C: для всех $1\le i<n$ выполняется $S_i\neq S_{i+1}$.
Для всех тестов гарантируется, что $1\le n\le 2\times 10^5$, а сумма длин строк по всем тестам в одном входном файле удовлетворяет условию $\sum n\le 2\times 10^5$. Строка $S$ содержит только строчные латинские буквы.