Cùng làm bài XÂU FIBINACCI nhé cả nhà
XÂU FIBINACCI
Xét dãy các xâu F1, F2, F3, …, FN, … trong đó:
F1 = ‘A’
F2 = ‘B’
FK+1 = FK + FK-1 (K 2).
Ví dụ:
F1 = ‘A’
F2 = ‘B’
F3 = ‘BA’
F4 = ‘BAB’
F5 = ‘BABBA’
F6 = ‘BABBABAB’
F7 = ‘BABBABABBABBA’
F8 = ‘BABBABABBABBABABBABAB’
F9 = ‘BABBABABBABBABABBABABBABBABABBABBA’
Cho xâu S độ dài không quá 25, chỉ bao gồm các ký tự ‘A’ và ‘B’. Hãy xác định số lần xuất hiện xâu S trong xâu FN, N 35. Chú ý: hai lần xuất hiện của S trong FN không nhất thiết phải là các xâu rời nhau hoàn toàn.
Dữ liệu: vào từ file văn bản FIBISTR.INP, bao gồm nhiều dòng, mỗi dòng có dạng N S. Giữa N và S có đúng 1 dấu cách. Dữ liệu vào là chuẩn, không cần kiểm tra.
Kết quả: Đưa ra file văn bản FIBISTR.OUT, mỗi dòng dữ liệu ứng với một dòng kết quả ra
Ví dụ:
FIBISTR.INP
3 A
3 AB
8 BABBAB
9 ABABB
FIBISTR.OUT
1
0
4
4
