파레이돌리아

*참고: 이 문제의 시간 제한은 기본의 2배인 4초이다.*

파레이돌리아(Pareidolia)는 실제로는 존재하지 않는 익숙한 패턴을 이미지에서 보게 되는 현상이다. 예를 들어 구름에서 얼굴을 보는 것이다. 짐작할 수 있듯이, 농부 존은 항상 소들 곁에 있다 보니 일상 사물에서 소와 관련된 패턴을 자주 본다. 예를 들어 문자열 "bqessiyexbesszieb"를 보면, 농부 존의 눈은 일부 글자를 무시하고 "bessiebessie"만 보게 된다.

문자열 \(s\)가 주어질 때, \(s\)에서 0개 이상의 문자를 삭제하여 만들 수 있는 "bessie"의 최대 반복 횟수를 \(B(s)\)라 하자. 위 예시에서 \(B(\)"bqessiyexbesszieb"\() = 2\)이다.

\(B(s)\)를 계산하는 것도 흥미로운 도전이지만, 농부 존은 더 흥미로운 도전을 풀고 싶어 한다. a-z 문자로만 이루어진 길이 \(3\cdot 10^5\) 이하의 문자열 \(t\)가 주어질 때, \(t\)의 모든 연속 부분 문자열 \(s\)에 대한 \(B(s)\)의 합을 계산하라.

출제자: Brandon Wang, Benjamin Qi

배점

• 입력 3-5: 문자열의 길이가 5000 이하이다.
• 입력 6-12: 추가 제약 조건이 없다.

출제자: Brandon Wang, Benjamin Qi

입력은 모든 문자가 영어 소문자인, 길이 \(3\cdot 10^5\) 이하의 비어 있지 않은 문자열로 이루어진다.

입력 문자열의 모든 부분 문자열에 걸쳐 만들 수 있는 bessie의 총 개수인 하나의 수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > US Open > Silver