Z-function and the minimum string period

Question

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

Answer 1

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.