给定字符串s,找到最短的字符串t,使得t ^ m = s.
例子:
s="aabbb" => t="aabbb"
s="abab" => t = "ab"
它能以多快的速度完成？
当然天真地,对于每m个除| s |,我可以尝试子串(s,0,| s |/m)^ m = s.
可以在O(d(| s |)n)时间内找出解,其中d(x)是s的除数.可以更有效地完成吗？
这是计算字符串周期的问题.Knuth,Morris和Pratt的顺序字符串匹配算法是一个开始的好地方.这是1977年题为"字符串中的快速模式匹配"的论文.
如果你想看中它,那么请查看Breslauer和Galil在1991年发表的论文"并行发现所有句号和初始回文".从他们的摘要中:
给出了用于计算字符串的所有周期的最佳O(log log n)时间CRCW-PRAM算法.以前的并行算法只有在短于字符串长度的一半时才计算周期.该算法可用于在同一时间和处理器范围内查找字符串的所有初始回文.两种算法在一般字母表中都是最快的.我们通过修改先前已知的下限找到一个字符串的周期来得到一个寻找回文的下界[3].当p处理器可用时,边界变为\ Theta(dnpe + log log d1 + p = ne 2p).