最长子字符串重复至少k次

Question

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

Answer 1

评论中进行了大量讨论，我认为最好写一个答案进行总结。 TL; DR Longest substring repeating atleast k times

[效率较低，但是比后缀树更容易理解：您需要知道的只是多项式哈希和二进制搜索。

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是按字符返回整数的函数（假设它是字符的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
也让我们预先计算数组pow中的p ^ 0％mod，p ^ 1％mod，...，p ^ len（s）％mod

# 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]倍，这解释了line a

。

b行

在使用% mod进行操作时有点神奇，a行之后的value可以为负，因此value%mod + mod肯定为正。同时，如果line a value大于value%mod + mod后mod为正，那么(value%mod + mod) % mod肯定会返回范围0，1，...，mod-1 。

最后，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，则有x个或更多个相等的子字符串，那么在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）

二进制搜索迭代，如果使用类似[ C0]检查是否存在> = k个哈希。我真的希望现在一切都清楚了。