8104번 - Fibonacci Words 다국어

Fibonacci words are defined similarly to Fibonacci numbers:

FIB₁ = b, FIB₂ = a, FIB_k+2 = FIB_k+1 ⊕ FIB_k for k ≥ 1,

where ⊕ denotes operation of connecting words (concatenation).

Hence we have: FIB₃ = ab, FIB₄ = aba, FIB₅ = abaab, FIB₆ = abaababa.

Write a program that:

• reads from the standard input a word comprising at least one and at most 30 characters a or b, and one positive integer n (n ≤ 200),
• computes how many times the word appears in the n-th Fibonacci word FIB_n (how many fragments of FIB_n are the same as the given word; the fragments may partially overlap),
• writes the result to the standard output.

In the first line of the standard input there is written one word. The word is composed of at least one and at most 30 characters a or b. In the second line there is written one positive integer n ≤ 200.

In the standard output there should be written one nonnegative integer. It should be equal to the number of times the given word appears in the Fibonacci word FIB_n.