最长子串至少重复 k 次

Question

我得到一个大长度的字符串（比如 100,000）和一个整数 k，我必须计算在给定字符串中至少重复 k 次的最大子字符串的长度。
我找到了这个特定问题的答案 here and here，但我想知道除了后缀树之外是否还有其他有效的方法来解决这个问题？

Answer 1

评论里讨论很大，我觉得还是写个回答总结一下比较好。长话短说

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

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

其中 ord 是一个函数 return 按字符输入整数（假设它是一个字符的 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) % mod 数组 pow:

# 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
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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

line b在% mod运算时有点神奇，line a之后的value可以是负数, 所以 value%mod + mod 肯定是正的。同时如果value在行a之后为正value%mod + mod大于mod，那么(value%mod + mod) % mod肯定会return 范围内的值 0, 1, ..., mod-1.

最后，mod 是一个大质数，如 10^9+7 而 value 是一个小数，但比任何可能的 ASCII 都大-代码像 239（在文章中阅读为什么这样）。

一些注意事项：

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

2。二分查找

只是在维基百科上阅读它，没有什么特别的 https://en.wikipedia.org/wiki/Binary_search_algorithm。

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

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

中有 k 或更多这样的子字符串

为什么二分查找在这里起作用？因为如果有一些长度x比如在长度x的s中有k个或更多相等的子串，那么在k中肯定有k个或更多相等的子串s 长度 x-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 的哈希。

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

最长子串至少重复 k 次

Longest substring repeating atleast k times

algorithm

performance

memory-efficient

data-structures

1.字符串多项式哈希

2。二分查找

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