서로 다른 부분 문자열 수

문제

문자열 $S$가 주어질 때, $S$의 서로 다른 부분 문자열의 개수를 구하여라.

부분 문자열은 문자열 내에서 연속한 문자들로 이루어진 문자열이다. 예를 들어 문자열 "abc"의 부분 문자열은 "a", "b", "c", "ab", "bc", "abc"의 6개이다.

모든 부분 문자열을 직접 생성하여 세면 시간이 오래 걸리므로, Suffix Array와 LCP 배열을 활용하여 효율적으로 구해야 한다. 접미사 배열의 각 접미사에서 만들 수 있는 부분 문자열의 개수는 접미사의 길이이며, 이웃한 접미사 간의 중복은 LCP 값만큼 빼주면 서로 다른 부분 문자열의 총 개수를 구할 수 있다.

입력

첫째 줄에 문자열 $S$가 주어진다.

제한

• $1 \le |S| \le 200,000$
• $S$는 소문자 알파벳(a-z)으로만 이루어진다.

출력

$S$의 서로 다른 부분 문자열의 개수를 출력한다.

예제 입력 1

aab

예제 출력 1

5

예제 입력 2

abc

예제 출력 2

6