find if a string is periodic using a suffix tree, and prove it
-
04-11-2019 - |
Question
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?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange