Для данной строки s найти самую короткую строку t, такую, что t ^ m = s

Для данной строки s найдите самую короткую строку t, такую, что t ^ m = s.

Примеры:

s="aabbb" => t="aabbb"
s="abab"  => t = "ab"

Как быстро это можно сделать?

Конечно, наивно, что для каждого m делит | s |, я могу попробовать, если substring (s, 0, | s | / m) ^ m = s.

Решение можно найти за время O (d (| s |) n), где d (x) - количество делителей s. Можно ли сделать это более эффективно?