給定字符串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的除數。它可以更有效地完成嗎？
這是計算字符串週期的問題。 Knuth, Morris and Pratt's sequential string matching algorithm是上手的好地方。這是從1977年的一篇題爲「字符串中的快速模式匹配」的文章。
如果您想要使用它，請查閱Breslauer的論文「查找並行字符串的所有句點和初始迴文」以及的Galil在1991年從他們的抽象：
最佳的爲O（log log n）的時間CRCW-PRAM算法用於計算串的所有 週期呈現。以前的並行算法只有在短於 字符串長度的一半時纔會計算該期間。該算法可以用於查找所有初始迴文 在同一時間和處理器範圍內的一個字符串。兩種算法都是在一般字母表上最快可能的 。我們通過修改先前已知的較低的 來找出迴文的下界 ，以尋找字符串的週期[3]。當p處理器爲 可用時，邊界變爲\ Theta（d n p e + log log d 1 + p = ne 2 p）。
一個修改博耶 - 穆爾在爲O（n）可能可能處理這個問題，其中n爲s
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
是的，你可以做到這一點的O(|s|)時間的長度。
您可以搜索一個長度爲n的「目標」字符串，長度爲m，長度爲O(n+m)。基於此建立解決方案。
讓源和目標都爲s。另外一個約束是1和源中不分的|s|的任何位置都不是有效的匹配起始位置。當然，搜索本身總是會失敗。但是如果存在部分匹配並且已經到達索引字符串的末尾，那麼您可以解決原始問題。
我真的很喜歡這個東西叫做Z-算法：http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
對於每一個位置，它計算從那裏開始的最長子，這也是整個字符串的前綴。 （當然是線性時間）。
a a b c a a b x a a a z
1 0 0 3 1 0 0 2 2 1 0
鑑於這種「Z-表」，很容易發現，可冪整個事情的所有字符串。只要檢查所有職位，如果pos+z[pos] = n。
在我們的例子：
a b a b
0 2 0
這裏pos = 2給你2+z[2] = 4 = n因此你可以用最短字符串的長度是2
這甚至讓你找到案件的一個只有前綴在指數化字符串匹配，喜歡的：
a b c a
0 0 1
這裏(abc)^2可減少到原來的字符串。但是，當然，如果你不想要這樣的比賽，只需要去除因子。