Problem: 

s0 = "a", s1 = "b", s2 = "ba", s3 = "bab", s4 = "babba", s4 = "babbabab", is called Fibonacci string. For the string with index n, given a string str = "bb", calculate how many times in the target?

Solution:

s2 =  s0+s1+the times in mid parts. 

Some cases "aaa", "bbb" or "abc" return 0 in advance. 

The code is :

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;


int countTimes(const string& haystack, const string& needle) {
    int count = 0;
    size_t found, len = needle.length(), pos = 0;
    while ((found = haystack.find(needle, pos)) != string::npos) {
        ++count;
        pos = found + len;
    }
    return count;
}

int calTimes(const string& str, int n) {
    string s0 = "a", s1 = "b", s2;
    int counts0 = s0 == str ? 1 : 0, counts1 = s1 == str ? 1 : 0, counts2 =counts0 + counts1;
    size_t slen = str.length(), s0len, s1len, s2len;

    //if (check3times(str))
    //    return 0;
    for (int i = 2; i <= n; ++i) {
        counts2 = counts0 + counts1;
        s2 = s1 + s0;
        s0len = s0.length(), s1len = s1.length(), s2len = s2.length();
        size_t s1r = min(s1len, slen), s0l = min(slen, s1len);
        string s0mid = s0.substr(0, s0l), s1mid = s1.substr(s1len-s1r, s1r), s2mid = s1mid + s0mid;
        counts2 += countTimes(s2mid, str);
        if (str == s0mid)
            --counts2;
        if (str == s1mid)
            --counts2;
        s0 = s1, s1 = s2, counts0 = counts1, counts1 = counts2;
    }
    return counts2;
}

int main() {
  string str1 = "a", str2 = "b", str3 ="abc";
  //int res1 = calTimes(str1, 6);
  //int res2 = calTimes("b",6);
  int res3 = calTimes("abba",6);

  return 0;
}