由于字符串s，找到最短的串T，这样，T ^ M = S。

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

例如：

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

多快能不能做到？

How fast can it be done?

当然天真，对于每m个分| S |，我可以尝试，如果子串（S，0，| S | / M）^ M = S。

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

一个可以计算出为O溶液（四（| S |）n）的时间，其中d（x）是第除数的数目。能不能更有效地完成？

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?

推荐答案

这是计算一个字符串的时期的问题。 高德纳，莫里斯和普拉特的连续字符串匹配算法是一个很好的地方开始。这是一个名为快速模式匹配的字符串从1977年纸。

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.

如果你想获得看上它，然后检查出纸找到所有的句号和并行字符串的初始回文经布雷斯劳尔和加利尔于1991年从他们的摘要：

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:

这是最佳的为O（log log n）的时间CRCW-PRAM算法来计算所有   字符串的周期为presented。 previous并行算法计算   期间只有当它是一半以上的长度的更短的   串。该算法可以被用来找到的所有初始回文   字符串以相同的时间和处理器界限。两种算法都   以最快的速度超过一般的字母表。我们得出一个下界   用于通过一个previously已知较低的变形发现回文   开往查找字符串[3]的期间。在p处理器   现有的界限变得\西塔（dnpe +登录登录D1 + P = NE 2P）。

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).