# List the lengths of all the prefix-suffixes in $O(n^{1+\epsilon})$ time

A proper prefix of a string $$s$$ that is also equal to a suffix of $$s$$ is called a PS (prefix-suffix).

Given a string $$s$$ of length $$n$$ is there an algorithm listing the lengths of all the PSs in $$O(n^{1+\epsilon})$$ time?

KMP can find the longest PS in linear time. Then we can note that the second longest PS is the longest PS of the longest PS so we can apply KMP iteratively but that is $$O(n^2)$$ in the worst case (e.g. if $$s=aaaa\dots a$$).