Строки Фибоначчи. Ошибка поиска совпадений

#include <iostream>
#include <string>

  using namespace std;

size_t elem_counting( const char *str, const char *substr ) {

	size_t cnt = 0, len = strlen( substr );

	for( ; str = strstr( str, substr ); str = str + len ) {
		cnt++;
	}

	return cnt;
}

int main() {

	const int n = 40;

	string str[46];

	str[0] = "A";
	str[1] = "B";

		for( int i = 2; i < n; i++ ) {
			str[ i ] = str[ i - 1 ] + str[ i - 2 ];
		}

	    cout<<elem_counting(str[35].c_str(),"BBABAB");

	return std::cin.get();
}

/*
  Функция elem_counting не правильно считает количество вхождений.
  Ошибка при n = 45;
*/

Есть у кого-нибудь решение этой задачи ?

Памяти не хватает, т.к. для 45-й строки надо 1,8 Гб. А ты еще предыдущие хранишь, это еще ~3 Гб.
Вот размеры строк

n байт 40 165580141 41 267914296 42 433494437 43 701408733 44 1134903170 45 1836311903

Dima T, что думаешь по поводу системы счисления Фибоначчи?

mayton
Dima T, что думаешь по поводу системы счисления Фибоначчи?

Если честно понятия не имею что это такое ))

Просто посчитал в экселе длину строки для этого цикла

for( int i = 2; i < n; i++ ) {
	str[ i ] = str[ i - 1 ] + str[ i - 2 ];
}

+

Не нашёл. Где-то было в форуме...

И как ему быть в таком случае ? Записывать в файл ? Или создавать тип данных особым образом хранящий строки (сжимающий их).

SashaMercury
И как ему быть в таком случае ? Записывать в файл ? Или создавать тип данных особым образом хранящий строки (сжимающий их).

Ему не нужны строки, ему нужно посчитать вхождение подстроки. Надо хранить не строку, а структуру типа {"N первых символов", кол-во вхождений, "N последних символов"} где N длина подстроки.

Тогда уже и вовсе никаких строк хранить не надо, достаточно убедиться, что начиная с какого-то значения n склеивание строк обязательно добавляет нужную подстроку и просто нужное число раз сложить пару чисел и 1.

wst,

уважаемый, на примере не покажете ?

смотрим первые строки такого типа:

0 B 0
...
5 BABBABABBABBA 1
6 BABBABABBABBABABBABAB 3
7 BABBABABBABBABABBABABBABBABABBABBA 4
8 BABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBABAB 8
...

Видно, что с какого-то момента строки либо кончаются на 'B', тогда в месте склейки получается 'BBABB' либо на 'BBA', тогда в месте склейки получается 'BBABAB', и это дело чередуется. Далее очевидно.