Assistance with Fibonacci words

[Kiyani]

Hello I'm trying to solve the Fibonacci word problem, I can't enter number greater than 41 because string size limit. Can someone give me suggestions? Thanks.

Here's my code

#include <iostream>
#include <string>
using namespace std;
void main()
{
	int loop = 0, count = 0, chk2 = 0;
	string first = "0";
	string second = "1";
	string ans, pattern;
	cout << "Enter number for fibb" << endl;
	cin >> loop;
	cout << "Enter pattern to check" << endl;
	cin >> pattern;

	for (int i = 1; i < loop; i++)
	{
		ans = second + first;
		first = second;
		second = ans;
	}

	for (int i = 0; i < ans.length(); i++)
	{
		if (pattern[count] == ans[i])
		{
			count++;
			
			if (count == pattern.length())
			{
				chk2++;
				count = 0;
				
				if(pattern.length()>1)
					if (pattern[0] == ans[i])
						i = i - 1;
			}
			
		}
		
	}
	
	cout <<"Number of Occurences is "<< chk2;
	
	

}

[Niccolo]

Let me guess, a 32 bit build?

Consider these sizes:

At i 32 len: 3524578
At i 33 len: 5702887
At i 34 len: 9227465
At i 35 len: 14930352
At i 36 len: 24157817
At i 37 len: 39088169
At i 38 len: 63245986
At i 39 len: 102334155
At i 40 len: 165580141
At i 41 len: 267914296
At i 42 len: 433,494,437

This shows the length of ans at each i from 32 to 42 (in a 64 bit build).

I put commas in that last one so you can tell it's over 400 Mbytes. At 41, when the string was 267,914,296 bytes long, the space required to perform the concatenation and the set the result was at least the volume of the destination plus the two source strings.

Considering that you also grow first and second in this loop, I expect that you'll hit the limit of RAM in a 32 bit build.

You can get a little further with a 64 bit build, but this expansion is close to geometric. It explodes.

This isn't the limit of the string class, this is about the limit of RAM.

You may be able to squeeze a little more out of the available space by calling reserve in advance for the overall space ultimately required by your target (so the concatenations don't require string expansion within the loop), but that will buy you only as much as the limit of RAM in your machine (if you set for 64 bit build).

In Windows in a 32 bit build you're limited to 2Gbytes unless you set the OS and the application with the "big switch" to allow up to 3Gbytes. After that you must move to 64 bit.

On Linux that doesn't apply, but you are still limited to 4 GBytes (less some change) in 32 bit builds.

[Ganado]

I'm unfamiliar with the "fibonacci word problem".

Your sequence seems to be identical to that of the original Algae L-system, with A = 1 and B = 0, except for your first iteration.
https://en.wikipedia.org/wiki/L-system#Example_1:_Algae

Perhaps that might be helpful in solving your problem.

Edit: I now see what you mean by fibonacci words.
https://en.wikipedia.org/wiki/Fibonacci_word

You might have to be smarter about how you make your pattern, because it blows up to a large size fairly quickly.
Apparently there is a similar closed-form sequence that might help you calculate what you want (the search patterns).
https://en.wikipedia.org/wiki/Fibonacci_word#Substitution_rules

[MikeStgt]

Can someone give me suggestions?

First: instead of strings of the two characters '0' and '1' (using only one of 8 bits), you could use bitsets to keep the pattern. See http://www.cplusplus.com/reference/bitset/bitset
Second: What do you hope to find unexpected in step past the 40th what did not show up to there?
Third: if you change

	string first = "1";
	string second = "0";

the resulting sequence would be the same as in the a. m. wiki. (Your loop starts with sequence step 2.)

[dutch]

you could use bitsets

Reducing the size by 8 only allows a few more steps.
And the search routine would be more complex.

BTW, for Fibonacci words the starting strings should be "0" and "01".

[dhayden]

Use string::find_first_of() to find the pattern.

[Ganado]

But they're trying to find the number of substrings, not just the first match.

[dutch]

You need an efficient search algorithm. (Boyer-Moore string search algorithm | https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm)

[jonnin]

can you store the strings in something *like* Huffman or other compression type encoding? That is say its term 5 at the wiki...

0100101001001
let a = 100
becomes 0a10aa1
so your storage shrinks as the thing gets bigger and you cut out bigger and bigger and multiple redundant terms...

this gets you a double payout: searching AND storage will BOTH be better.

[MikeStgt]

this gets you a double payout: searching AND storage will BOTH be better.

You may continue replacement of patterns, for example for n=2..25 the strings would be

01
010
01001
01001010
0100101001001
010010100100101001010
0100101001001010010100100101001001
0100101001001010010100100101001001010010100100101001010
... and so on

Now, replacing 01 by a, a0 by b, ba by c and so on 22 times, you get

a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
vu
vuv

Thus accrues a lucidity and illuminative transparency that was perfectly hidden before by a vast oodles of 0s and 1s.

[dutch]

I don't think such a scheme will gain much.

[jonnin]

you don't think the strings will be subject to compression type reduction?

[MikeStgt]

I don't think such a scheme will gain much.

How do you define gain in this context?

What I did with this series of replacements is the reversal of the building process. Result of step 2 is a, of step 3 is b, and so on. The gain could be the insight, that there is no need to continue with it ad infinitum. After a-b-c and d and e followed by f ... some time will come z. No need to go further, even no need to go so far. It's all determined in the building specification.