0
$\begingroup$

A string s of length n is periodic if there is a string $u$ of length <= n/2 such that $s = u^ku'$, where $k$ is an integer >=2, $u^k$ is the concatenation of k copies of $u$ , and $u'$ is a prefix of u.

The smallest period of $s$ is the shortest $u$ (largest $k$) for which this holds.

For example, if s=ACACACACA, then k=4, u=AC, u'=A.

I want a linear-time algorithm for determining if s is periodic.

This SO answer gives a nice lead for a suffix tree solution. I want to use it, but I can't prove that it will work if and only if s is periodic.

Can you sketch it for me?

$\endgroup$
2
$\begingroup$

It's wrong. Consider $aaaabb$, so you'll find that $aaa$ repeat twice and consider it as an answer, while it is obviously not.

Check each suffix with length $n>l\ge\frac{n}{2}$. If it's also a prefix of $s$, $s$ is periodic and $u$ is the prefix with length $n-l$. If you can't find such suffix $s$ is not periodic. The proof is straight forward: $s[i]=s[i+n-l]$ for $1\le i \le l$. So you can easily prove that $s[n-l+1..2(n-l)]=u$, and so on. Since $n-l\le\frac{n}{2}$, $u$ repeat at least twice. The converse is similar, by proving $s[i]=s[i+len(u)]$.

KMP or Z-algorithm are sufficient to do this, but if you really need a suffix tree solution:

Check each node on the path from root to the leaf which represents the whole string. If a node on this path represents a suffix with length $\ge\frac{n}{2}$ (except the whole string), we find the answer. (Note that each node on this path represents a prefix.)

$\endgroup$
  • $\begingroup$ great! can you share an intuition on how did you think of this solution? it seems trivial now, but I couldn't see it before :( $\endgroup$ – ihadanny Jan 21 '17 at 15:52
  • 1
    $\begingroup$ @ihadanny Actually the simplest way to define "periodic" is $s[i+P]=s[i]$ where $P$ is the period. In other word, $s$ keeps the same if we "shift" it by $P$. Now it's not hard to see we're matching a suffix with a prefix. $\endgroup$ – aaaaajack Jan 21 '17 at 18:26

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.