Biarkan aku mendengar suaramu, ceritakan kisah-kisah dalam perjalananmu—
Baik hal-hal yang menyenangkan maupun yang menyakitkan, juga pertemuan-pertemuan yang terukir di hati.
Deskripsi Soal
Diberikan sebuah string $S$ dengan panjang $n$, yang indeksnya dimulai dari $1$. Notasi $S(i, j)=S_iS_{i+1}\cdots S_j$ menyatakan substring dari $S$ yang terdiri atas karakter ke-$i$ hingga karakter ke-$j$.
Jika string tak kosong $B$ merupakan prefiks sekaligus sufiks dari string $X$, dan $|B|<|X|$, maka $B$ disebut sebuah Border dari $X$, dengan $|X|$ menyatakan panjang string $X$.
Pada awalnya, kamu berada di substring $S(1, n)$. Setiap lompatan dilakukan sebagai berikut:
- Pilih sebuah substring $X$ di dalam substring tempatmu berada saat ini.
- Pilih sebuah Border $B$ dari $X$ yang memenuhi $2|B|\ge |X|$.
- Lompat ke substring yang bersesuaian dengan kemunculan $B$ sebagai prefiks atau sufiks dari $X$; kamu boleh memilih salah satu dari keduanya.
Sebagai contoh, jika $S$ adalah aabaaba dan kamu berada di $S(1, 7)$, kamu dapat memilih $X=S(2, 7)=$ abaaba. Border-nya, aba, memiliki panjang tepat setengah dari $|X|$, sehingga kamu dapat melompat ke $S(2, 4)$ atau $S(5, 7)$.
Untuk setiap $1\le i\le n$, tentukan secara terpisah jumlah lompatan maksimum yang dapat dilakukan jika dimulai dari $S(1, n)$ dan akhirnya mencapai $S(i, i)$. Jika tidak dapat dicapai, jawabannya adalah $-1$. Kamu diperbolehkan untuk tidak melakukan lompatan sama sekali.
Terdapat beberapa kasus uji.
Masukan
Baris pertama berisi sebuah bilangan bulat $T$, yang menyatakan banyaknya kasus uji.
Selanjutnya, setiap kasus uji diberikan secara berurutan. Setiap kasus uji terdiri atas satu baris yang menyatakan string $S$.
Keluaran
Untuk setiap kasus uji, keluarkan satu baris berisi $n$ bilangan bulat. Bilangan bulat ke-$i$ menyatakan jawaban untuk $S(i, i)$ (jika $S(i, i)$ tidak dapat dicapai, keluarkan -1).
Contoh
Masukan 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Keluaran 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
Catatan
Pada kasus uji pertama, $S=$ abbababbab, dan prefiks serta sufiksnya yang memiliki panjang $5$ sama-sama berupa abbab. Dua lompatan berikut dapat dilakukan:
- Pertama, lompat ke $S(1, 5)$, lalu pilih $S(2, 3)=$ bb dan lompat ke $S(2, 2)$ atau $S(3, 3)$.
- Pertama, lompat ke $S(6, 10)$, lalu pilih $S(7, 8)=$ bb dan lompat ke $S(7, 7)$ atau $S(8, 8)$.
Lompatan hanya dapat dilanjutkan jika lompatan pertama menuju salah satu dari dua abbab di atas, dan lompatan berikutnya hanya dapat mencapai satu karakter. Oleh karena itu, jumlah lompatan maksimum untuk keempat posisi tersebut masing-masing adalah $2$.
Posisi-posisi lainnya tidak dapat dicapai melalui lompatan, sehingga jawabannya adalah $-1$.
Contoh 2
Lihat wind2.in dan wind2.ans pada lampiran. Contoh ini memenuhi batasan subsoal 3.
Contoh 3
Lihat wind3.in dan wind3.ans pada lampiran. Contoh ini memenuhi batasan subsoal 5.
Contoh 4
Lihat wind4.in dan wind4.ans pada lampiran. Contoh ini memenuhi batasan subsoal 6.
Contoh 5
Lihat wind5.in dan wind5.ans pada lampiran. Contoh ini memenuhi batasan subsoal 8.
Batasan
Ketergantungan antarsubsoal yang sesuai diberlakukan pada soal ini.
| Subsoal | $n\le$ | $\sum n\le$ | Sifat Khusus | Nilai |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | Tidak ada | $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$ | Tidak ada | $12$ |
Sifat khusus A: Terdapat string tak kosong $P$ sedemikian sehingga $S$ merupakan prefiks dari string berulang tak hingga $P^{\infty}$, dan $|P|\le 10$.
Sifat khusus B: $S$ dibangkitkan secara acak, yaitu setiap karakter $S$ dipilih secara acak dengan peluang seragam dari himpunan karakter berukuran $\ge 2$.
Sifat khusus C: Untuk semua $1\le i<n$, berlaku $S_i\neq S_{i+1}$.
Untuk semua data, dijamin $1\le n\le 2\times 10^5$, dan jumlah panjang string dari seluruh kasus uji dalam satu berkas uji memenuhi $\sum n\le 2\times 10^5$. String $S$ hanya berisi huruf kecil bahasa Inggris.