Period of a finite binary sequence

Question

Let $G:N\to\{0,1\}$, and let $L$ be some period of $G$, so that $G(i+kL)=G(i)$. What's the best a good way to find the smallest period of $G$? I mean an algorithm that takes ($G$,$L$) and outputs the smallest period.

Answer 1

Let $G[m,n]$ denote the string formed by the values of $G$ between based indices $m$ and $n$ (inclusive). (Here all indices are $1$-based.)

Use a string matching algorithm to locate the first occurrence of the string $G[1,L]$ within the string $G[2,2L]$. The index of this occurrence is equal to the minimal period.

You can easily find linear-time string matching algorithms off the shelf (for instance, Knuth-Morris-Pratt can be implemented in a dozen lines of code). With a bit more care you could probably read off the period from the prefix table rather than performing an explicit query.

Answer 2

You could take the discrete Fourier transform of $G$ on $[1,2,\ldots,L]$. If $g$ is the GCD of those $k$ where the Fourier transform is nonzero, the minimal period is $L/g$.