# Find shortest prefix to generate original string by overlapping

Given a string $$S$$, I want to find the prefix string $$P$$ of shortest length, such that the original string $$S$$ can be generated by concatenating copies of $$P$$ (where overlapping is allowed).

For example, if $$S = atgatgatatgat$$, I want to find $$P = atgat$$; $$P$$ is the smallest prefix of $$S$$ that can be concatenated (in this case three times, starting at indices $$\{0,3,8\}$$ of $$S$$, where the first and second copies overlap but the second and third copies do not overlap) to equal $$S$$.

Obviously, there is an $$\mathcal{O}(n^2)$$ algorithm by checking each prefix of $$S$$, but a colleague mentioned it might be possible to do it in $$\mathcal{O}(n \log n)$$. I'm thinking of using suffix arrays for different prefixes of $$S$$ but haven't quite been able to proceed from there.

You are asking about "quasiperiodicity". This is a well-studied topic and a google scholar search will turn up many papers about it. For example, there is an $$O(n (\log n)^2)$$ algorithm here and an $$O(n \log n)$$ algorithm here.
• I just noticed the OP has cross-posted on this site as well after I posted my answer here. Since OP is only interested in the shortest substring (which coincides with the prefix of $S$ of length equal to the quasiperiodicity) that covers $S$ there exists an $O(n)$ algorithm. – orlp Nov 30 '18 at 15:38