最长重复子串 高频面试题 题解

题目：
就是说有一个字符串s，比如'banana'，然后你要求出来它最长的重复子串是什么？ 
那什么叫最长重复子串呢？
首先，它是子串，是连续的子串这无需多言。
重复就是说不止出现一次
最长就是最长的那个。
所以最长重复子串就是 ‘最长的那个’ ‘重复过的’ ‘连续子串’。
最后，如果没有重复子串，请输出空串:''

字符串长度是10^5数量级

样例：
input
'banana'

output
'ana'

input 
'abcd'

output
''

这道题在华为二面出现过，在美团二面出现过，因此本人想要对此作出解析。这道题我看LC上甚至有什么Rabin-Krap，真滴恐怖（见都没见过），所以还是学了一个简单的常见的解法，希望能够抛砖引玉。

常规解法很好想：就是遍历所有长度，然后每一个子串都检查一下是不是重复出现，这里遍历要耗时n，检查重复也要耗时n（哈希表），所以是O(n^2)

那么，有没有能够优化的地方呢？ 这里其实很好想，根据字符串10^5量级，一般就是要nlogn的复杂度，所以会联想到logn的一些算法，比如二分查找。

我们仅优化'遍历'，把遍历所有长度，变成二分查找所有长度，就可以达到目的。 在我们的主函数中二分，如果当前长度满足条件就暂时保存这个答案，贪心地继续寻找更长的答案直到结束二分，在check函数中结合哈希表判断是否重复过。

代码如下：

class Solution:
    def longestDupSubstring(self, s: str) -> str:
      
      def check(cur_len):
        cnt = Counter()
        for i in range(len(s)):
          if i+cur_len>len(s):break
          if s[i:i+cur_len] in cnt:
            return s[i:i+cur_len]
          else:cnt[s[i:i+cur_len]] = 1
        return ''

      left,right = 0,len(s)
      res = ''
      while left<right:
        mid = (left+right)//2
        cur = check(mid)
        if cur=='':right = mid
        else:
          if len(res)<len(cur):res = cur
          left = mid+1
      return res