I have some binary sequence that contains a binary string that repeats itself. For example: $$ 11001001\,\,\, 11001001 \ldots $$ I want to build a table with two columns. The left column is a sub string of the sequence that has a length $N$ and the right column contains the next bit. I would like to find the minimal $N$ to be the length of the binary strings so the next bit is known for sure.
For example, if I take $N=2$ then for $00$ we know for sure that we will have $1$ but for $01$ we could have $0$ or $1$. After some investigation of the example above I found out that the minimal $N$ is $5$. I had to go from through $1,2,3,4,5$ to figure it out.
My question is as follows: Is there some method or equation to find the minimal $N$ in general binary sequence without having to go through the neutral numbers starting from $1$?
The longest repeated substring in one cycle of your sequence is $1001$; your $N$ is its length plus one. You can find the longest repeated substring with a suffix array computation, in time $O(p)$ or $O(p\log p)$ in the period $p$ of your original sequence.