algorithm - Given string s, find the shortest string t, such that, t^m=s

Question

Given string s, find the shortest string t, such that, t^m=s.

Examples:

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

How fast can it be done?

Of course naively, for every m divides |s|, I can try if substring(s,0,|s|/m)^m = s.

One can figure out the solution in O(d(|s|)n) time, where d(x) is the number of divisors of s. Can it be done more efficiently?

Answer 1

This is the problem of computing the period of a string. Knuth, Morris and Pratt's sequential string matching algorithm is a good place to get started. This is in a paper entitled "Fast Pattern Matching in Strings" from 1977.

If you want to get fancy with it, then check out the paper "Finding All Periods and Initial Palindromes of a String in Parallel" by Breslauer and Galil in 1991. From their abstract:

An optimal O(log log n) time CRCW-PRAM algorithm for computing all periods of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of the string. This algorithm can be used to find all initial palindromes of a string in the same time and processor bounds. Both algorithms are the fastest possible over a general alphabet. We derive a lower bound for finding palindromes by a modification of a previously known lower bound for finding the period of a string [3]. When p processors are available the bounds become Theta(d n p e + log log d1+p=ne 2p).