문자열 순위

소문자 영어 알파벳으로 이루어진 문자열 $w$와 $u$가 있다. 정수 수열 $i_1, \cdots, i_k$가 엄격하게 증가하고, $|w| = n$, $|u| = k$이며, 모든 $j = 1, \dots, k$에 대해 $u[j] = w[i_j]$이면 $u$를 $w$의 부분 수열이라고 한다. $v[i]$는 문자열 $v$의 $i$번째 문자이다. $w[i:]$는 접미 문자열 $w[i] \cdots w[n]$을 뜻하고, $i > n$이면 $w[i:]$는 빈 문자열 $\lambda$이다.

비어 있지 않은 문자열 $w$와 양의 정수 $k$에 대해, $w$의 $k$-집합 $Q_k(w)$는 길이가 $0, 1, \cdots, k$인 $w$의 부분 수열 전체의 집합이다. 이 정의에 따라 빈 문자열 $\lambda$는 항상 $Q_k(w)$에 속한다.

예를 들어 $w$가 aaba일 때, $Q_3(\text{aaba}) = \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}, \text{aab}, \text{aaa}\}$이다.

$w$의 순위는 $w$의 모든 접미 문자열의 $t$-집합이 서로 모두 다르게 되는 최소의 정수 $t$이다. 형식적으로는 $\min\{t \ge 1 \mid Q_t(w[i:]) \ne Q_t(w[j:]) \text{ 모든 } 1 \le i < j \le n \text{ 에 대해}\}$이다.

예를 들어 $w$가 aaba일 때, $Q_2(\text{aba})$와 $Q_2(\text{aaba})$는 같다. $t = 3$일 때 접미 문자열의 집합은 $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}\}$이다. 다섯 집합이 모두 다르므로 aaba의 순위는 3이다.

입력은 소문자 영어 알파벳으로만 이루어진 비어 있지 않은 문자열 $w$ 하나이다. $w$의 길이는 $3 \times 10^6$ 이하이다.

정확히 한 줄에 $w$의 순위 $t$를 양의 정수로 출력한다.