# 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 <= 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>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)]$.
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.)
• @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. – aaaaajack Jan 21 '17 at 18:26