P14775 [ICPC 2024 Seoul R] String Rank

Let $ w $ and $ u $ be strings consisting of the English lowercase alphabet. We say that a string $ u $ is a subsequence of a string $ w $ if there exists a strictly increasing sequence of integers $ i_1, \dots, i_k $, where $ |w| = n $, $ |u| = k $ and $ u[j] = w[i_j] $ for all $ j = 1, \dots, k $. Here, $ v[i] $ denotes the $ i $-th character of the string $ v $. Let $ w[i:] $ denote the suffix $ w[i] \cdots w[n] $. If $ i > n $, then $ w[i:] $ is the empty string denoted by $ \lambda $. Given a nonempty string $ w $ and a positive integer $ k $, we define the $ k $-set of $ w $ to be the set $ Q_k(w) $ of subsequences of $ w $ whose lengths are $ 0, 1, \dots, k $. This implies that, for any string $ w $, the empty string $ \lambda $ belongs to $ Q_k(w) $ by definition. For example, when $ w = \text{aaba} $, we have $ Q_3(\text{aaba}) = \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}, \text{aab}, \text{aaa}\} $. For a string $ w $, we define the rank of $ w $ to be the minimum integer $ t $ such that the $ t $-sets for all suffixes of $ w $ are all different. In other words, the rank of $ w $ is $ \min\{t \geq 1 \mid Q_t(w[i:]) \neq Q_t(w[j:]), \forall 1 \leq i < j \leq n\} $. For instance, when $ w = \text{aaba} $, the 2-sets $ Q_2(\text{aba}) $ and $ Q_2(\text{aaba}) $ are equal. On the other hand, for $ t = 3 $, we have $$ \begin{aligned} Q_3(\lambda) &= \{\lambda\}, \\ Q_3(\text{a}) &= \{\lambda, \text{a}\}, \\ Q_3(\text{ba}) &= \{\lambda, \text{a}, \text{b}, \text{ba}\}, \\ Q_3(\text{aba}) &= \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}\}, \\ Q_3(\text{aaba}) &= \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}, \text{aab}, \text{aaa}\}. \end{aligned} $$ Therefore, the rank of the string $ w = \text{aaba} $ is 3. Given a string $ w $, write a program to output its rank.

Your program is to read from standard input. The input consists of a single nonempty string $ w $, which consists only of lowercase characters from the English alphabet. The length of the string is at most $ 3 \times 10^6 $.

Your program is to write to standard output. Print exactly one line. The line should contain a positive integer to represent the rank $ t $ of the input string $ w $.