32839번 - 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, \cdots , 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, \cdots , k$. This implies that, for any string $w,ドル the empty string $\lambda$ belongs to $Q_k(w)$ by definition.

For example, when $w = $aaba, we have $Q_3($aaba$) = \{\lambda,ドル a, b, ba, ab, aa, aba, aab, 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 ≥ 1 | Q_t(w[i:]) \ne Q_t(w[j:]), ∀1 ≤ i < j ≤ n\}$.

For instance, when $w = $aaba, the 2ドル$-sets $Q_2($aba$)$ and $Q_2($aaba$)$ are equal. On the other hand, for $t = 3,ドル we have

• $Q_3(\lambda) = \{\lambda\},ドル
• $Q_3($a$) = \{\lambda,ドル a$\},ドル
• $Q_3($ba$) = \{\lambda,ドル a, b, ba$\},ドル
• $Q_3($aba$) = \{\lambda,ドル a, b, ba, ab, aa, aba$\},ドル
• $Q_3($aaba$) = \{\lambda,ドル a, b, ba, ab, aa, aba, aab, aaa$\}$.

Therefore, the rank of the string $w = $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$.

제한

힌트