Question

Let $\Sigma = \{ \sigma_1 , ..., \sigma_t \}$ and let $S$ be a string from $\Sigma^*$. Denote: $n=|S|$, that is $S$ has $n$ letters. I'd like to find the shortest prefix $T$ of $S$ such that $S$ is a prefix of $T^n$ ($T^n= T \cdot .... \cdot T$, $n$ times).

I tried to build the suffix tree for $S$, and then checking each node, by their levels - from lowest level to top level, because then the corresponding prefix will be shortest at the lowest level of the suffix tree and will get longer - and then for each node checking if this property applies for the prefix of the current suffix node I'm looking at, but that would not necessarily give me the shortest prefix, because the suffix tree may have on the same level different lengths suffices.

I'm not sure as to how I'll be able to find the shortest prefix $T$? Perhaps there is a different way of using a suffix tree?

Or maybe there is a way to solve this efficiently without using suffix trees at all?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top