Seems like all the solutions here are really n^4. The only possible way I can see an n^3 solution is if you preprocess the original string to find all equal sub strings via hashing.
There's O(n^2) sub problems for each substring.
When you want to see if a string can be broken up into 'k' parts, you need to potentially try breaking the string up into 1, 2, 3... k parts. This is an O(n) loop. (Actually, perhaps this is really a sqrt(n) loop since you only have to try divisors up to the sqrt(n).. so perhaps we can get O(n^3*sqrt(n))
To check if all 'k' parts are equal takes O(n) time. So in total, it would take O(n^4)... am I missing something?
Actually, it looks like many of the solutions are using the (s+s).find(s, 1, -1) trick to avoid trying each possible number of ways there are to split a string into "k" equal parts.