君の声を聞かせて、旅の物語を教えて——
楽しかったことも、つらかったことも、そして心に刻まれた出会いも。
問題文
長さ $n$ の文字列 $S$ が与えられます。添字は $1$ から始まります。$S(i, j)=S_iS_{i+1}\cdots S_j$ と書き、$S$ の $i$ 番目の文字から $j$ 番目の文字までからなる部分文字列を表します。
空でない文字列 $B$ が文字列 $X$ の接頭辞であると同時に接尾辞でもあり、$|B|<|X|$ を満たすとき、$B$ を $X$ の Border と呼びます。ここで、$|X|$ は文字列 $X$ の長さを表します。
最初、あなたは部分文字列 $S(1, n)$ にいます。1 回のジャンプを次のように行います。
- 現在いる部分文字列の中から、部分文字列 $X$ を選びます。
- $2|B|\ge |X|$ を満たす $X$ の Border $B$ を選びます。
- $B$ が $X$ の接頭辞として現れる部分文字列、または接尾辞として現れる部分文字列にジャンプします。どちらを選んでもかまいません。
例えば、$S$ が aabaaba で、あなたが $S(1, 7)$ にいるとき、$X=S(2, 7)=$ abaaba を選ぶことができます。その Border aba の長さはちょうど $|X|$ の半分なので、$S(2, 4)$ または $S(5, 7)$ にジャンプできます。
各 $1\le i\le n$ について、$S(1, n)$ から出発して最終的に $S(i, i)$ に到達するときのジャンプ回数の最大値を求めてください。到達できない場合、答えは $-1$ です。ジャンプを一度も行わなくてもかまいません。
複数のテストケースがあります。
入力
1 行目には整数 $T$ が与えられます。これはテストケース数を表します。
続いて各テストケースが順に与えられます。各テストケースでは、文字列 $S$ を表す 1 行が与えられます。
出力
各テストケースについて、$n$ 個の整数を 1 行に出力してください。$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
注記
1 番目のテストケースでは、$S=$ abbababbab であり、長さ $5$ の接頭辞と接尾辞はいずれも abbab です。次のように 2 回のジャンプを行うことができます。
- まず $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)$ にジャンプします。
最初のジャンプで上記の 2 つの abbab のいずれかに移った場合に限り、さらにジャンプできます。その次のジャンプでは 1 文字にしか到達できないため、これら 4 つの位置へのジャンプ回数の最大値はすべて $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$ が保証され、1 つの入力ファイル内のすべてのテストケースの文字列の長さの総和は $\sum n\le 2\times 10^5$ を満たします。文字列 $S$ は英小文字のみからなります。