# Z-function and the minimum string period

Let $$s$$ be a string of length $$n$$. One of the classical solutions to the problem of finding the smallest period $$p$$ of $$s$$ (that is, smallest $$p$$ such that $$s$$ can be obtained as a concatenation of the several copies of $$p$$) uses so-called $$Z$$-function. In words, $$Z=Z[0..n]$$ with $$Z[0] = 0$$ and $$Z[i]$$ is the length of the longest substring starting at position $$i$$ which coincides with some prefix of $$s$$. Given that, it is easy to solve the problem of the smallest period: we iterate through $$i$$, and if at some point we find $$i$$ such that $$i + z[i] = n$$ and $$n$$ modulo $$i$$ is $$0$$, then $$s[0..i-1]$$ is our answer.

Now back to the question. Suppose $$s$$, as before, is a prefix (of length no more than, say, $$10^6$$) of an infinite string $$ppppppppp...$$ obtained by concatenation of infinitely many copies of $$p$$. The goal is to recover the smallest possible $$p$$. Can we adopt the algorithm above to solve the problem?

Example: $$s = abcabca$$, the answer is $$p=abc$$.

If at some point we find $$i$$ such that $$i + z[i] \ge n$$, then the smallest possible $$p$$ is $$s[0..i-1]$$.
• The proof for the correctness of this approach is almost the same for the case of finding the smallest pure period of $s$. It looks like there is no question on the latter case. – John L. Jun 20 at 4:07