logo标签列表

给定字符串s，找到最短的字符串t，使得t的m次方等于s。

stringalgorithm
8

给定字符串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$的因子数量。是否可以更有效地完成呢？

4个回答
5
这是计算字符串周期的问题。 Knuth，Morris和Pratt的顺序字符串匹配算法是一个很好的起点。这在一篇名为“Fast Pattern Matching in Strings”的论文中提到，时间是1977年。
如果您想进行高级操作，请查看Breslauer和Galil于1991年发表的论文“并行查找字符串的所有周期和初始回文”。从他们的摘要中可以看出：
引用： 提出了一种最优的O（log log n）时间CRCW-PRAM算法，用于计算字符串的所有周期。 先前的并行算法仅在周期短于字符串长度的一半时才计算周期。 这个算法可以用来在相同的时间和处理器限制下找到字符串的所有初始回文。 两个算法都是通用字母表中可能的最快速度。 我们通过修改先前已知的查找字符串周期的下限[3]来推导出找到回文的下限。 当p处理器可用时，边界变为\ Theta（d n p e + log log d1 + p = ne 2p）。
4

我非常喜欢这个叫做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可以缩减为您原始的字符串。但是，如果您不想匹配这样的内容，只需仅查看除数即可。

2

是的，您可以在O(|s|)时间内完成。

您可以在O(n+m)时间内，在长度为m的“源”字符串中搜索长度为n的“目标”字符串。基于此构建解决方案。

让源和目标都为s。一个额外的限制是，1和不被|s|整除的任何位置都不是匹配的有效起始位置。当然，搜索本身总是失败的。但是，如果存在部分匹配并且已经到达了源字符串的末尾，则您就有了解决原始问题的方法。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接