피보나치 문자열

시간 제한1초메모리 제한1024 MB

요약

X의 모든 부분 문자열 중에서 연속한 두 a가 없는 문자열(피보나치 문자열)에 대해, 그 안에 들어 있는 a의 개수를 모든 등장 위치마다 더한 값을 구한다.

문제

Aron은 피보나치 수를 좋아한다. 너무 좋아한 나머지 수 자체에는 흥미를 잃고, 그것을 바탕으로 다른 조합적 대상들을 만들어 내기로 했다.

그의 첫 번째 발명품은 피보나치 문자열이다. $a$ 와 $b$ 로만 이루어지고, $a$ 가 정확히 $n$ 개 있으며 $a$ 가 연속으로 두 번 나오지 않는 문자열을 $n$ 번째 피보나치 문자열이라고 부른다.

$a$ 와 $b$ 로 이루어진 문자열 $X$ 가 주어질 때, $X$ 의 부분 문자열 중 피보나치 문자열인 것들의 계수의 합을 구하라. 문자열 $X$ 가 여러 번 나타나면, 그 계수를 나타난 횟수만큼 더해야 한다.

채점기는 입력을 다음 형식으로 읽는다.

채점기는 fibonacci(N, X)의 반환값을 한 줄에 출력한다.