0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.