All periods in string I want to find all the periods in a string. Moreover, I want to do it in a linear time and using a prefix function. I've noticed a pattern, that I want to generalize to an algorithm, though, unfortunately, I am not able to achieve O(len(s)) time, so I'd like to get some clues, how to optimize the algorithm.

Here is what I came to. Consider a string and prefix function (just like in KMP algorithm):

abababab

00121234

I have noticed, that if we have a period of length t, then in indices k * t for natural k >= 2 value of prefix function is >=t. The problem is that if I'd check all the prefixes of given string to satisfy this condition, then it would obviously take O(len(s)^2) time. What can be done to improve the speed of the algorithm?
This is already way too late. But shouldn't this be $O(n \log{n})$? $n$ being $len(s)$. You are doing $\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n} $ work, which integrates to $n \ln{n}$. 

Prefix function precomputation is $O(n)$, so it wouldn't matter.
This is already way too late. But shouldn't this be $O(n \log{n})$? $n$ being $len(s)$. You are doing $\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n} $ work, which integrates to $n \ln{n}$. 

Prefix function precomputation is $O(n)$, so it wouldn't matter.