find if a string is periodic using a suffix tree, and prove it A  string s of  length n is  periodic  if  there  is  a  string $u$ of  length &lt;= 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?
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&gt;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.)