题目描述

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$.

aabbb

3

abacb

2

azadzzadaz

4

a

1