파레이돌리아
시간 제한4초메모리 제한1024 MB
소문자로 이루어진 길이 30만 이하의 문자열 t가 주어질 때, t의 모든 부분 문자열 s마다 "bessie"를 부분 수열로 몇 번 만들 수 있는지 B(s)를 구하고 그 합을 구합니다.
문제
파레이돌리아는 실제로는 없는 곳에서 익숙한 무늬를 보는 현상이다. 구름에서 얼굴을 보는 것이 그 예이다. 존 농부는 소와 늘 가까이 지내서, 일상의 사물에서도 소와 관련된 무늬를 자주 본다. 예를 들어 문자열 "bqessiyexbesszieb"를 보면, 눈이 일부 글자를 무시해서 "bessiebessie"로 보인다.
문자열 가 주어졌을 때, 는 에서 0개 이상의 문자를 지워서 "bessie"를 최대 몇 번 반복해서 만들 수 있는지를 나타낸다. 위 예에서 이다.
존 농부는 이보다 더 흥미로운 문제를 풀고 싶어 한다. 길이가 최대 이고 영문 소문자로만 이루어진 문자열 가 주어졌을 때, 의 모든 연속 부분 문자열 에 대한 의 합을 구하시오.
입력
입력은 길이가 최대 인 비어 있지 않은 문자열이며, 모든 문자는 영문 소문자이다.
출력
한 개의 수를 출력한다. 이 수는 입력 문자열의 모든 연속 부분 문자열에서 만들 수 있는 bessie의 총 개수이다.