1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

If at some point we find $i$ such that $i + z[i] \ge n$, then the smallest possible $p$ is $s[0..i-1]$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Jun 20 at 4:07

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.