파레이돌리아(pareidolia)는 일반적으로 영상이나 소리 등의 자극을 통해 전혀 관련이 없는 패턴을 느낌으로써 이에 심적으로 반응하는 심리적 현상이다.

곰돌이 마을의 학자로 유명한 곰 배씨(bessie)는 본인의 이름과 비슷한 문자열을 읽을 때 파레이돌리아 현상을 느끼곤한다.

예를 들어, "bqessiyexbesszieb"라는 문자열을 보면 배씨는 일부 문자를 무시하고 "bessiebessie"만 보게 된다.

문자열 s가 있을 때, B(s)는 s에서 0개 이상의 문자를 제거하였을 때 "bessie"가 반복하여 나오는 최대 횟수를 의미한다.

ex) B("bqessiyexbesszieb")=2.

학자 곰들 사이에서는 B(s)를 계산하는 것이 매우 흥미로운 도전으로 여겨진다.

그런데, 배씨가 이 도전을 더 흥미롭게 만드는 제안을 하였다.

최대 길이 3⋅10^5의 a-z로만 이루어진 문자열 t가 주어지면, t의 모든 연속하는 부분 문자열 s에 대한 B(s)를 계산하는 것이다.

학자 곰 (Pareidolia) timer 4s memory 1024MB

학자 곰 (Pareidolia) 4s 1024MB