시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB90351869.231%

문제

문자열 a와 b로만 이루어진 문자열 S가 있다. S에서 겹치지 않게 두 번 등장하는 S의 부분 문자열 P는 좋은 부분 문자열이다.

S = "aaaabb" 인 경우에 좋은 부분 문자열은 "a", "aa", "b"가 있다. "aaa"는 두 번 등장하지만, 겹쳐서 등장하기 때문에 좋은 부분 문자열이 아니다.

문자열 S가 주어졌을 때, 서로 다른 좋은 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. 문자열 S의 길이는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문자열 S의 서로 다른 좋은 부분 문자열의 개수를 출력한다.

예제 입력 1

aaaa

예제 출력 1

2

예제 입력 2

aaaabb

예제 출력 2

3

예제 입력 3

bbaabb

예제 출력 3

3

예제 입력 4

babbaaaaab

예제 출력 4

5

예제 입력 5

abbaabaaabb

예제 출력 5

9

예제 입력 6

aaaaaaaabbaaabbaaaaaaababaaaababaaaaaaaaaabaaaaaaab

예제 출력 6

63

출처