비교 불가능한 쌍

시간 제한3초메모리 제한512 MB

요약

문자열 s의 부분 문자열 쌍 가운데 서로가 상대의 부분 문자열이 아닌 쌍의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 문자열, 트리, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

문자열 $s = s_1 s_2 ... s_n$ 이 주어진다. $s$ 의 부분 문자열로 이루어진 순서 없는 쌍 $\{a, b\}$ 를 생각하자. $a$ 가 $b$ 의 부분 문자열도 아니고 $b$ 가 $a$ 의 부분 문자열도 아니면, 이 쌍을 비교 불가능한 쌍이라고 한다. $s$ 의 부분 문자열 중 비교 불가능한 쌍의 개수를 구하라.

입력

첫째 줄에 소문자 영어 알파벳으로 이루어진 문자열 $s$ 가 하나 주어진다 ( $1 \le |s| \le 10^5$ ).

출력

답을 나타내는 정수 하나를 출력한다.

예제2

예제 1
입력
```
abba
```
예상 출력
```
8
```
예제 2
입력
```
abacaba
```
예상 출력
```
64
```