「JSOI2019」节日庆典_信奥算法NOI/NOI+/CTSC-ACGO题库

JYY 和探险队顺利完成了火星上的任务。在离开前，探险队正好赶上了火星人一年一度最盛大的节日「气球节」。然而，火星人遇到了每年一度的麻烦：怎样最美观地摆放气球。JYY 决定请你设计算法帮助火星人解决这个问题。

在庆典开始前，火星人会把气球准备好并串在一根绳子上。气球按顺序排列可以看成是一个由小写字母组成的长度为 $n$ 的字符串 $S$ 。然后，火星人会按照字符串的顺序逐个把气球加入到一个庆典的圆环上，并且表演一个节目庆祝。

下图展示了一串气球 cbbadbcd 在进行到第 $5$ 个节目时的情形，此时在庆典环上的气球是 cbbad。

为了让每个节目都更好看，火星人希望在每个节目开始前调整气球在环上的顺序，使得每个节目的气球排布都最美观。对于一组气球（一个字符串），火星人认为最美观的字符串是庆典圆环上按绳子方向读出字典序最小的字符串，例如对于 cbbad，共有 $5$ 个读出字符串的位置：

如果有多个字典序最小的字符串，火星人希望找出离绳头最近的那个(即 $i$ 最小的那个)。更严谨地说，对于字符串 $T$ ，定义

$T_i = T[i\ldots |T|] :: T[1\ldots i-1]\ (1\le i \le |T|)\textrm{，}$

其中 $::$ 是字符串的拼接操作。定义 $f(T)$ 为最小的 $i$ （ $1\le i \le |T|$ ）满足 $T_i = \min\{T_1,T_2,\ldots,T_{|T|}\}$ 。

JYY希望你帮助他设计一个算法，让火星人每个节目的气球排列都最美观，即对于给定字符串 $S$ 的每一个前缀 $S[1\ldots i]$ （ $1\le i \le |S|$ ），求出 $f(S[1\ldots i])$ 。

输入只有一行，该行包括一个字符串 $S$ 。

在一行中对于每个 $i$ （ $1\le i\le |S|$ ），输出一个整数 $f(S[1\ldots i])$ 。输出的数字之间以空格分隔。

测试点	$n$	是否随机生成	生成限制
$1$	$\le 20$	否	无
$2,3$	$\le 10^3$	是	字符集为 $\{\texttt{a,b,c}\}$
$4$	$\le 2\times 10^5$	是	字符集为 $\{\texttt{a,b,c}\}$
$5$	$\le 5\times 10^4$	否	每个字符出现次数相等
$6,7$	$\le 10^6$	否	无
$8,9,10$	$\le 3\times 10^6$	否	无

A85881.「JSOI2019」节日庆典