Let's prove there are always only two prefixes required if it's possible. Let's say we get the answer with more than two strings: $$$s_1, s_2, ..., s_k$$$. Then we can get a string $$$s_1 + s_2 + ... + s_{k - 1}$$$ using only one prefix.

So all we have to do is to find the suffix, such that it is a prefix either. You can do it using Z-function

UPD: I'm quite stupid I guess

We can solve it using simple polynomial hash method.

For each prefix, we can calculate the hash value of it. And then, we can try to copy it a lot of times, calculating the hash value as the same time, until the length exceed n.

Time complexity is $$$\sum_{i = 1} ^ {n} [n / i] = \Theta(n log n).$$$