algorithm - 最长重复至少 k 次的子串

评论中有大量讨论，我认为最好写一个答案来总结。TL;DR最长重复至少 k 次的子串

有一种效率较低的方法，但它确实比后缀树更容易理解：您只需要知道多项式哈希和二进制搜索即可。

1.字符串多项式哈希

在这里阅读https://cp-algorithms.com/string/string-hashing.html。以下是该技术的简短描述。

假设我们有字符串s、整数p和mod. 现在我们可以定义哈希函数：

hash(s) = (ord(s[0])*p^(len(s)-1) + ord(s[1])*p^(len(s)-2) + ... + ord(s[len(s)-1])*p^0) % mod

whereord是一个按字符返回整数的函数（假设它是一个字符的 ASCII 码）。可以很容易地为O(len(s))中字符串的每个前缀计算多项式哈希：

# h[i] is a hash of prefix of length i.
# For example s = "abacaba",
# h[0] = hash("") = 0
# h[1] = hash("a")
# h[2] = hash("ab")
# ...
# h[7] = hash("abacaba")

h[0] = 0
for i in 1..n:
    h[i] = (h[i-1] * p + ord(s[i-1])) % mod

另外让我们预先计算数组中的p^0 % mod, p^1 % mod, ..., p^len(s) % modpow：

# pow[i] is (p^i) % mod
pow[0] = 1
for i in 1..n:
    pow[i] = (pow[i-1] * p) % mod

使用数组h，pow我们可以轻松计算字符串的任何子字符串的哈希s：

# get_substring_hash returns hash(s[l] + s[l+1] + ... + s[r-1]).
def get_substring_hash(s, l, r):
    value = h[r] - h[l]*pow[r-l]    # line a
    return (value%mod + mod) % mod  # line b

让我们了解为什么上面的代码有效。

h[r] = (ord(s[r-1])*p^0 + ord(s[r-2])*p^1 + ... + ord(s[l-1])*p^(r-l) + ord(s[l-2])*p^(r-l+1) + ...) % mod
h[l] = (                                          ord(s[l-1])*p^0     + ord(s[l-2])*p^1       + ...) % mod
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

如您所见，我们只需要^^^-part from，h[r]因此我们必须摆脱~~~-part。~~~-part inh[r] p^(r-l)比 in 大h[l]，这解释了a 行。

% mod与一起操作时，b 行有点神奇， a 行value之后可以是负数，所以肯定 make 是正数。同时如果在a 行大于之后为正，那么肯定会返回0, 1, ..., mod-1范围内的值。value%mod + modvalue value%mod + modmod(value%mod + mod) % mod

最后，mod是一个大素数，如10^9+7，value是一个小数，但比任何可能的 ASCII 码（如239 ）都大（请参阅文章为什么如此）。

一些注意事项：

哈希可能会发生冲突，因为我们只有mod可能的哈希值，但字符串的数量是无限的。如何处理它在文章中阅读。
执行类似的操作h[r] - h[l]*pow[r-l]可能需要使用 64 位类型的整数。

2.二分查找

只需在 Wikipedia 上阅读它，没有什么具体的https://en.wikipedia.org/wiki/Binary_search_algorithm。

3. 最长重复至少k次的子串解

假设我们预先计算了数组h和pow. 让我们进行二进制搜索以找到字符串的最大长度，以便在给定ans的字符串中存在k或更多这样的子字符串s。

为什么二进制搜索在这里有效？因为如果有一些长度x，例如在长度中存在k或更多相等的子字符串，那么在长度中肯定有或更多相等的子s字符串（只需从我们的匹配项中删除最后一个字母）。xksx-1

二分搜索将如何工作？假设我们目前正在测试是否有k或多个相等的长度子串mid。我们将计算所有长度的哈希值mid（使用get_substring_hash），如果k哈希值相等，我们将决定更改二进制搜索的边界。

例如：s = "abcabcdefgdefgdefgdefg", k = 3。答案是“defgdefg”：

abcabcdefgdefgdefgdefg
      ^^^^^^^^          occurence 1
          ^^^^^^^^      occurence 2
              ^^^^^^^^  occurence 3

二分搜索迭代：

l =  1, r = 22, mid = 11. No substring of length 11 satisfy.
l =  1, r = 10, mid =  5. There should be hash("defgd")    be seen 3 times.
l =  5, r = 10, mid =  7. There should be hash("defgdef")  be seen 3 times.
l =  7, r = 10, mid =  8. There should be hash("defgdefg") be seen 3 times.
l =  8, r = 10, mid =  9. No substring of length 9  satisfy.
l =  8, r =  8.           That means answer is 8.

如您所见，复杂度为O(n log n)：round(log n)二进制搜索迭代和O(n)每次迭代的复杂度，如果您使用类似std::unordered_map检查是否存在>= k出现的散列。

我真的希望现在一切都清楚了。

algorithm - 最长重复至少 k 次的子串

问题描述

解决方案

1.字符串多项式哈希

2.二分查找

3. 最长重复至少k次的子串解

推荐阅读