题目：
给你一个字符串 s ，考虑其所有 重复子串 ：即，s 的连续子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 “” 。

思路：
参考官方题解：https://leetcode-cn.com/problems/longest-duplicate-substring/solution/zui-chang-zhong-fu-zi-chuan-by-leetcode-0i9rd/
重复子串可能的长度m 的取值范围为：[1,n-1] ,其中n=len(s)

• 对m进行二分查找：若存在长度为m的重复子串，则更新left=m+1，并更新重复子串的最大长度 和 重复子串的起点；若不存在，则令right=m-1。
• 对指定m进行判定，为防止碰撞，此处采用了双哈希：
  （1）求出两种进制下，字符串的哈希编码；
  （2）求n-m+1个长度为m的子串中，是否存在重复：
  以字符串“abcdabc"举例，假定当前子串长度m=3，n=7，则长度为3的子串共有7-3+1个。
  
  第二个子串"bcd"的编码，采用原始计算的方式如下：
  也可利用h0的计算结果，进行进一步的计算：
  根据上述过程可进一步推导得出：
  
  

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-duplicate-substring/solution/zui-chang-zhong-fu-zi-chuan-by-leetcode-0i9rd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解答：

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        # 生成两个进制
        a1, a2 = random.randint(26, 100), random.randint(26, 100)
        # 生成两个模
        mod1, mod2 = random.randint(10**9+7, 2**31-1), random.randint(10**9+7, 2**31-1)
        n = len(s)
        # 先对所有字符进行编码
        arr = [ord(c)-ord('a') for c in s]
        #print(arr)
        # 二分查找重复子串的长度，其范围是[1, n-1]
        l, r = 1, n-1
        length, start = 0, -1
        while l <= r:
            m = l + (r - l + 1) // 2
            #判断s中是否有长度为m的重复子串,若有则返回重复子串的起点
            idx = self.check(arr, m, a1, a2, mod1, mod2)
            # 有重复子串，移动左边界，更新重复子串的最大长度length
            if idx != -1:
                l = m + 1
                length = m
                start = idx
            # 无重复子串，移动右边界
            else:
                r = m - 1
        return s[start:start+length] if start != -1 else ""
    
    #检查arr中是否有长度为m的重复子串
    def check(self, arr, m, a1, a2, mod1, mod2):
        n = len(arr)
        #al1,al2分别为a1^m,a2^m
        aL1, aL2 = pow(a1, m, mod1), pow(a2, m, mod2)
        h1, h2 = 0, 0
        #计算两种进制下(a1和a2)的字符串编码
        for i in range(m):
            h1 = (h1 * a1 + arr[i]) % mod1
            h2 = (h2 * a2 + arr[i]) % mod2
        # 存储一个编码组合是否出现过
        seen = {(h1, h2)}
        #求n-m+1个长度为m的子串中，是否存在重复
        for start in range(1, n - m + 1):
            h1 = (h1 * a1 - arr[start - 1] * aL1 + arr[start + m - 1]) % mod1
            h2 = (h2 * a2 - arr[start - 1] * aL2 + arr[start + m - 1]) % mod2
            # 如果重复，则返回重复串的起点
            if (h1, h2) in seen:
                return start
            seen.add((h1, h2))
        # 没有重复，则返回-1
        return -1