파일 복구

시간 제한5초메모리 제한128 MB

요약

주어진 문자열에서 두 번 이상 나타나는 서로 다른 연속 부분 문자열의 개수를 각 테스트 케이스마다 구한다. 문자열 길이는 최대 100000이다.

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

문제

학교에는 웹 서버로 쓰이는 컴퓨터가 한 대 있다. 이 서버는 학교 공식 홈페이지, 교직원 개인 페이지, 연구실 사이트, 과목 페이지 등 수많은 사이트를 호스팅한다.

최근 하드디스크의 파일 테이블이 손상되어 모든 파일의 구조 정보가 사라졌고, 백업도 없다. 유일한 방법은 디스크 전체를 훑어보며 각 파일에 해당하는 부분을 직접 찾아내는 것이다. 다행히 이 파일 시스템은 각 파일을 연속된 바이트 덩어리로 저장했으므로, 연속된 조각만 살펴보면 된다.

디스크 데이터는 바이트의 나열이다. 각 바이트에는 64가지 문자 중 하나가 담긴다. 즉 영문자(대문자와 소문자를 구별한다), 십진 숫자, 마침표 ., 쉼표 , 중 하나다.

또한 이 파일 시스템은 각 파일의 여러 복사본을 유지했으므로, 어떤 연속된 바이트 조각이 파일이 될 수 있으려면 그 조각이 두 번 이상 반복되어 나타나야 한다. 그리고 반복되는 조각마다 복사본 하나만 검사하면 된다. 예를 들어 데이터가 ababcabb라면 연속 조각 a, b, ab는 반복되지만, c를 포함하는 어떤 조각도, ba도, bb도 반복되지 않는다. 따라서 검사해야 할 연속 바이트 조각은 $3$ 개다.

디스크 데이터에서 두 번 이상 나타나는 서로 다른 연속 부분 문자열의 개수, 즉 검사해야 하는 조각의 수를 정확히 계산하는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정확히 한 줄로 주어지며, 디스크 데이터를 나타내는 길이 $1$ 이상 $10^5$ 이하의 문자열이다. 각 문자는 소문자, 대문자, 숫자, 마침표 ., 쉼표 , 중 하나다. 마지막 테스트 케이스 다음 줄에는 별표 * 하나만 있는 줄이 온다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 값은 해당 문자열에서 두 번 이상 나타나는 서로 다른 연속 부분 문자열의 개수다.

예제2

예제 1

입력

ababcabb
mississippi
aaaaaaaaaaaaaaaaaaaaaaaaaa
012345678,abcdefg.STUVWXYZ
say.twice,say.twice
*

예상 출력

예제 2
입력
```
aa
*
```
예상 출력
```
1
```