# Lời giải bài Xâu FIBONACI

###### 📌 Tags: `Simple` .
____
## Ý tưởng :+1:
* Trong C++ việc cộng xâu là

    string a , b;
    a = a +b;

* sau đó ta liên tưởng đến việc tìm trong xâu F[n] có xâu SR hay không
____
## Nhận xét :bulb:
* Để tìm xâu Sr có trong xâu F[n] hay không và đếm số lượng bằng cách nào
* Vì string trong c++ hoạt động như là một mảng (lưu ý mảng kiểu string có phần tử đầu tiên là ở chỉ số không và giá trị lưu luôn là char(ký tự) )
-> Ví dụ : string st = "abc";
phần tử đầu tiên là st[0] = 'a'; (mỗi phần tử của string được viết thành char )
* Vậy bài toán viết về đơn giản là với mảng $F[n]$ ta so sánh bằng việc chọn một vị trí bắt đầu so từng phần tử của mảng $F[n]$ với từng phần tử của $sr$ . Hay nếu chọn $i$ làm vị trí bắt đầu thì ta phải so sánh $F[n][i]$ với $sr[0]$ , $F[n][i + 1]$ với $sr[1]$ , ... , $F[n][i + sr.length() - 1]$ với $sr[sr.length() - 1]$ nhưng phải đảm bảo $i + sr.length() - 1 \le F[n].length() - 1$ vì việc xâu con liên tiếp của $F[n]$ mà có độ dài bé hơn xâu sr thì xâu sr bằng xâu con đó là **không thể**.
* Thuật này không sợ quá thời gian vì độ dài lớn nhất có thể có của $F[n] \le 10^6$ và độ dài của xâu $sr \le 35$ nên độ phức tạp lớn chỉ là $O(10^6 * 35)$ **(đã được kiểm chứng bằng nộp)**
____