测试数据来自 nnu_contest/1301

H. String Shifting

时间限制:5s

空间限制:512MB

本题分值:300

题目描述

按以下方法定义字符串的”左移“：

• 将字符串的第一个字符移动到字符串的末尾。例如， \(abcde\) 左移一次后变为 \(bcdea\)

设某字符串长度为 \(n\) ，其经过 \(0,1,...,n-1\) 次左移，可以得到 \(n\) 个字符串 \(s_0,s_1,...s_{n-1}\)。

请对于每一个 \(0\le i\le n-1,i\in \N\) ，输出集合 \(\{s_0,s_1,...s_{n-1}\}\) 中比 \(s_i\) 字典序小的字符串个数。

输入格式

仅一行，包含一个字符串\(s\)

输出格式

共 \(n\) 个整数，表示答案

样例输入1

aaba

样例输出1

1 2 3 0

样例1解释

\(s_0=aaba\)，\(s_1=abaa\)，\(s_2=baaa\)，\(s_3=aaab\)

其中字典序满足\(s_3<s_0<s_1<s_2\)。

所以：比\(s_0\)小的字符串有\(1\)个，比\(s_1\)小的字符串有\(2\)个，比\(s_2\)小的字符串有\(3\)个，比\(s_3\)小的字符串有\(0\)个。

样例输入2

aaaa

样例输出2

0 0 0 0

样例输入3

JYACWaUZK

样例输出3

2 6 0 1 5 8 4 7 3 

样例输入4

pVFvXDDoPoZaTDuGbhjqmixUACNstgyCcORYcnGtEqlXhyAZPjsHYLsHvFApFeNRXllVqohfFzPBLHclSmSskiWxtNYYMDeAliTyluMTjJNbuWPrvAVDFlTSzrAsnpxBSjCLMGOQNHwmPCpBuDBzRoFuTGJgVOfJvoYIafTGpYbpnnBDoYfuLPXDzaEhEYgFYzdeARWqGFhQdpHneopZGHPqRFKFmFjmMdOAfEcKJmRuZopKhrIWWpTAPXacVFxlUxbbzHwAJyTWGcxtXZcDKkwbzyXJJmSczInngupxWjZfpHcqfqzCUprWpXPdfxxdgjWxueWmQDKRYPbTbUNYZXkvJXQTLzuXhibAwsWHVAJbBBHgpqaFztKYsJeBIoCRhEsXRbGZfuBpiOFklDhzQUihaxAyfTytBLoZtkCDw

样例输出4

337 168 57 388 183 31 37 323 128 326 210 218 151 39 376 66 228 275 290 352 313 284 397 161 0 25 115 366 372 268 407 28 235 119 140 202 238 315 69 368 45 351 302 192 277 406 6 208 127 291 359 72 196 104 360 77 386 47 9 332 50 250 111 138 194 304 301 171 353 328 273 254 59 416 121 17 100 73 237 298 147 312 148 364 293 281 181 402 370 112 199 197 106 35 248 8 303 280 159 411 305 378 108 158 286 85 114 230 380 174 130 358 385 5 167 32 54 299 155 149 421 355 10 365 320 345 396 19 146 285 24 101 107 64 118 132 110 79 392 308 122 29 331 21 375 30 22 418 143 322 56 379 152 63 89 264 170 120 255 92 389 324 195 81 220 256 153 68 339 201 229 342 318 314 14 38 325 203 261 377 102 123 184 41 419 216 44 269 42 204 263 49 206 420 243 247 4 137 180 347 61 51 271 135 246 334 76 316 252 330 340 207 62 70 129 348 136 48 94 55 306 52 289 307 109 242 116 7 253 43 234 95 90 310 144 382 214 329 335 98 276 356 80 175 178 336 150 3 124 190 219 236 169 58 401 300 165 399 227 231 414 78 390 2 93 408 156 172 67 240 403 371 189 211 233 34 99 296 391 232 424 409 185 84 91 311 145 241 415 82 319 317 267 384 346 398 176 288 212 258 333 74 239 350 259 354 413 27 164 344 357 179 338 186 126 244 262 405 400 245 265 287 182 404 383 251 177 309 131 33 96 139 198 125 225 157 226 162 113 200 209 193 295 387 86 187 133 154 105 423 381 191 274 282 222 11 394 362 173 71 166 1 87 223 13 15 75 266 343 349 217 60 422 369 97 205 361 88 249 16 83 321 26 142 270 46 363 188 141 224 65 213 260 374 20 341 279 117 53 294 297 36 278 417 134 163 283 272 221 395 12 410 257 160 412 367 18 103 327 215 373 292 23 40 393

数据范围及限制

字符串中的字符仅包含 小写字母或大写字母。设\(n\)是字符串的长度

测试点编号	约定	测试点分值
1~2	\(2\le n\le 10\)，字符串中所有字符均为小写字母\(a\)	每个测试点15分
3~4	\(2\le n\le 10\)	每个测试点15分
5~6	\(2\le n\le 500\)	每个测试点20分
7~8	\(n = 2^{18}\)	每个测试点50分
9~10	\(2\le n\le 2^{18}\)	每个测试点50分