当前位置:   article > 正文

leetcode刷题日记-1044. 最长重复子串_给定一个长度为 n,全部由小写英文字母组成字符串 s,找出最长的子串,使得该子串在

给定一个长度为 n,全部由小写英文字母组成字符串 s,找出最长的子串,使得该子串在
  • 题目描述:
    给你一个字符串 s ,考虑其所有重复子串 :即,s 的连续子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
    返回 任意一个 具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 “” 。

  • 示例:
    输入:s = “banana”
    输出:“ana”
    输入:s = “abcd”
    输出:""
    2 <= s.length <= 3 * 104
    s 由小写英文字母组成

  • 解析,这道题目的难度指数为困难,也确实很难,考的知识点很多,但是其实每个知识点都不难,难得是如何想到这些知识点以及如果组合这些知识技巧。这种困难的题目一般都是考优化,暴力破解基本是不可能通过的,一般都要进行优化。暴力破解虽然肯定通过不了,但是这是我们考虑问题、进行优化的出发点,所以如果不是一眼就能看出这道题怎么优化,还是需要从暴力破解出发。

  • 第一步,如何暴力破解呢?我们考虑到题目 给你一个字符串 s ,考虑其所有连续子串中重复的,并且返回最长的那个。首先字符串s最长的子串是其本身,但是没有重复,所以不满足题意,没有重复子串的情况很好判断,如len(set(s)==len(s)即可判断,这种情况我们先不考虑。我们考虑有重复子串的情况,那么其长度范围为(1, n-1),其中n为字符串s的长度,那么我们暴力破解的思路就来了,我们再将问题简化:假设给定一个定长k,假设这个定长的子串一定重复,返回s中出现的第一个子串。这个题目是不是就很容易想到滑动窗口来解决,即固定一个定长的子串,一直往后遍历,每个k子串的时间复杂度是(n-k)*k,k为滑动窗口长度,字符串匹配时间复杂度为O(k),那么所有k子串的时间复杂度就是(n-k)*(n-k)*k,前面提到的滑动窗口长度(1, n-1),时间复杂度为O(n),总得时间复杂度最起码是O(n3)。

  • 第二步,考虑如何优化,首先滑动窗口的选择能不能优化?答案当然是可以的,面对在一个有序区间找一个值得最好办法肯定是二分,二分思路是这样的,如果在n/2处能够找到重复子串的话,那么其最长重复子串一定大于等于n/2,反之,则一定小于等于n/2,通过这个思路可以将第一层循环的时间复杂度O(n)变成O(log n)。

  • 第三步,完成第二步优化之后,总时间复杂度为O(n2 log n) ,仍然不能通过,,说明还需要进行优化,这里可以优化的地方只有滑动窗口了,我们需要这里的O(n2)接着往下降,这里就可能可以想到Rabin-Karp算法,想不到没关系,下次一定。Rabin-Karp算法是一种字符串匹配算法,将匹配时间复杂度降低到了O(n),所以我们最后的时间复杂度为O(n log n),通过!Rabin-Karp算法的原理其实很简单,就是讲每个子串进行哈希,如本题,都是小写字母,我们可以用ASCII编码来表示,这样原字符串就变成了一个数组,我们将这些数组分成m(滑动窗口长度)长的子串,由于小写字母共有26个,因此我们可以用26进制来表示m长子串对应的hash值,如果两个字符串匹配,那么其hash值一定相等,但是考虑到hash冲突,两个不一样的子串hash值也可能相等,这里有两种解决办法,一是用多个进制,比如用27进制和29进制,这样hash冲突的可能性大大减少,但是还是有一定可能,二是hash值相等时,直接比较其对应的两个字符串,这样时间复杂度虽然会高点,时间复杂度需要多乘以一个m,这样本题也无法通过,但是可以完全避免hash冲突。
      这里附上两个参考链接,感觉讲的不是很清楚,下期更新一下Rabin-Karp算法的原理和实现。

  • Rabin-Karp算法:字符串匹配问题

  • Rabin-Karp算法详解和实现(python)

  • 两个hash来弱化冲突的解法如下(官方思路):

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        """
        给你一个字符串 s ,考虑其所有 重复子串 :即,s 的连续子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠 	              
        >>>self.longestDupSubstring("banana")
        >>>"ana"
        """
        # 生成两个进制
        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)
        arr = [ord(c)-ord('a') for c in s]   
        def check(arr, m, a1, a2, mod1, mod2):
            n = len(arr)
            aL1, aL2 = pow(a1, m, mod1), pow(a2, m, mod2)
            hash1, hash2 = 0, 0
            for i in range(m):
                hash1 = (hash1 * a1 + arr[i]) % mod1
                hash2 = (hash2 * a2 + arr[i]) % mod2
            seen = {(hash1, hash2)}
            for start in range(1, n - m + 1):
                hash1 = (hash1 * a1 - arr[start - 1] * aL1 + arr[start + m - 1]) % mod1
                hash2 = (hash2 * a2 - arr[start - 1] * aL2 + arr[start + m - 1]) % mod2
                if (hash1, hash2) in seen:
                    return start
                seen.add((hash1, hash2))
            return -1
        left, right = 1, len(s)-1
        ans, maxLength = -1, 0
        while left <= right:
            mid = left + (right - left + 1) // 2
            repeatIndex = check(arr, mid, a1, a2, mod1, mod2)
            if repeatIndex != -1:
                left = mid+1
                ans = repeatIndex
                maxLength = mid
            else:
                right = mid - 1
        return s[ans:ans+maxLength] if ans != -1 else ""
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 完全避免hash冲突的解法如下(力扣时间复杂度无法通过):
from collections import defaultdict
def longestDupSubstring(s):
    """
    给你一个字符串 s ,考虑其所有 重复子串 :即,s 的连续子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠 	     >>>longestDupSubstring("nnpxouomcofdjuujloanjimymadkuepightrfodmauhrsy")
    >>>"ma"
    """
    arr = [ord(c)-ord('a') for c in s]
    modulo = 2**64-1
    def check(arr, m):
        visited = defaultdict(list)
        hashM = 0
        for i in range(m):
            hashM = hashM*26 + arr[i]
        visited[hashM%modulo].append(0)
        for j in range(m, len(arr)):
            hashM = hashM - arr[j-m]*(26**(m-1))
            hashM = (hashM*26 + arr[j])%modulo
            if hashM in visited.keys():
                for v in visited[hashM]:
                    if s[j-m+1:j+1] == s[v:v+m]:
                        return v
            visited[hashM].append(j-m+1)
        return -1
    
    left, right = 0, len(s)-1
    ans, maxLength = -1, 0
    while left <= right:
        mid = (left + right) // 2
        repeatIndex = check(arr, mid)
        if repeatIndex != -1:
            left = mid+1
            ans = repeatIndex
            maxLength = mid
        else:
            right = mid - 1
    return s[ans:ans+maxLength] if ans != -1 else -1 
     
s = "nnpxouomcofdjuujloanjimymadkuepightrfodmauhrsy"
longestDupSubstring(s)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 如果大家觉得有帮助,欢迎点个免费的赞,谢谢!在这里插入图片描述
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/182210
推荐阅读
相关标签
  

闽ICP备14008679号