이상한 문자열
시간 제한1초메모리 제한512 MB
문자열 s가 주어질 때, 부분 문자열의 집합과 부분 수열의 집합이 같은 문자열 t의 서로 다른 부분 문자열 개수를 센다.
문제
알파벳 소문자로 이루어진 문자열 를 생각하자. 예를 들어 «abba»가 그러한 문자열이다.
문자열 의 부분문자열이란 에서 연속한 한 개 이상의 문자를 이어 붙여 만든 문자열이다. 의 모든 부분문자열을 모은 집합을 라 하자. 이때 같은 부분문자열이 에 여러 번 나타나더라도 집합에는 한 번만 들어간다.
예를 들어 이다.
문자열 의 부분수열이란 에서 임의의 개수의 문자를 지워 얻을 수 있는 문자열이다. 의 모든 부분수열을 모은 집합을 라 하자. 와 마찬가지로, 의 부분수열이 여러 가지 방법으로 얻어지더라도 에는 한 번만 들어간다. 의 모든 부분문자열은 의 부분수열이기도 하므로 는 를 포함하지만, 다른 문자열을 더 포함할 수도 있다.
예를 들어 이다. 기호 는 집합의 합집합을 나타낸다.
이면 문자열 를 이상한 문자열이라 하자. 예를 들어 «abba»는 이상한 문자열이 아니지만, «abb»는 이므로 이상한 문자열이다.
문자열의 이상함이란 그 문자열의 서로 다른 이상한 부분문자열의 개수이다. 이상함을 계산할 때 어떤 부분문자열이 에 여러 번 나타나더라도 한 번만 센다. 예를 들어 «abba»의 이상함은 7이며, 전체 문자열을 제외한 모든 부분문자열이 이상한 문자열이다.
주어진 문자열 의 이상함을 구하는 프로그램을 작성하라.
입력
입력 파일에는 알파벳 소문자로 이루어진 문자열 가 주어진다. 문자열의 길이는 1 이상 200,000 이하이다.
출력
출력 파일에는 입력 파일에 주어진 문자열의 이상함을 나타내는 정수 하나를 출력한다.