给定字符串s,找到最短的字符串t,使得$t^m=s$。
示例:
s="aabbb" => t="aabbb"
s="abab" => t = "ab"
需要多快才能做到?
当然,可以单纯地对每个$m$除以$|s|$,并尝试判断是否满足子字符串$s$的前$|s|/m$个字符被重复了$m$次。
可以用$O(d(|s|)n)$的时间找到解决方案,其中$d(x)$是$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
可以缩减为您原始的字符串。但是,如果您不想匹配这样的内容,只需仅查看除数即可。
是的,您可以在O(|s|)
时间内完成。
您可以在O(n+m)
时间内,在长度为m
的“源”字符串中搜索长度为n
的“目标”字符串。基于此构建解决方案。
让源和目标都为s
。一个额外的限制是,1和不被|s|
整除的任何位置都不是匹配的有效起始位置。当然,搜索本身总是失败的。但是,如果存在部分匹配并且已经到达了源字符串的末尾,则您就有了解决原始问题的方法。
对 Boyer-Moore 的修改可能能以 O(n)(其中 n 是 s 的长度)的时间处理此问题。
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm