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.