string - 求字符串 S 的最短前缀 T，使得 S 是 T^n 的前缀

Question

我们使用的总体思路是使用贪心算法检查字符串的剩余部分并进行比较。

这个想法没有奏效，一般的想法可能是使用某种后缀树或 KMP 算法，但我尝试的一切都失败了。

有人可以帮忙吗？

PS：T^n 是前缀乘以 n，因为 n 是字符串的长度，字符串之间的字母是 [1..n]

Answer 1

我会像在Rabin karp algorithm中一样使用滚动哈希。首先加倍 S，以便您确定 T^n 是 S*S 的前缀。

接下来迭代 T 的长度。对于每个长度，您可以以对数复杂度计算 T^n 的哈希码（非常类似于二进制求幂）。此外，在对 S*S 进行线性预计算之后，您可能会在恒定时间内找到其每个子字符串的哈希码（您需要一个包含所有前缀哈希的数组和一个包含您正在使用的素数的幂的数组用于散列）。所以你可以检查每个长度 if T^n == SUBSTRING(S^2, n * LENGTH_OG(T)) in O(log(n)) （在这里你应该考虑一下如何花时间计算哈希每次迭代的 t 常数）。因此，所提出的方法的总体复杂度将为 O(LENGTH(S) * Log(LENGTH(S)))。

希望这可以帮助。

编辑：我相信我已经找到了问题的线性解决方案。正如您所说，它基于KMP。在为您的字符串计算故障函数后，观察它的值。以案例为例：

string s = "abcdababcdababcdababcdababc";

值如下：

   a     b     c    d    a    b    a    b    c    d    a    b    a    b    c    d    a    b    a    b    c    d    a    b    a    b    c  
 -001  -001  -001  -001  000  001  000  001  002  003  004  005  006  007  008  009  010  011  012  013  014  015  016  017  018  019  020

看看你在最终指数中的价值。我相信如果你从 S 的长度中减去它然后再减去一个，你会得到最短重复子串的长度。在此示例中，您有27 - 20 - 1 = 6. 在我上面展示的情况下更容易观察 - 当故障函数以 0 到 20 的值序列结束时。但事实上，如果你有一些以 20 结尾的其他值，那么 0 到 20 将再次成为有效值故障功能它只会跳过一些可能性。希望这是有道理的。该算法是线性的。