1044. 最长重复子串

Difficulty

Hard

Tags

动态规划

URL

https://leetcode-cn.com/problems/longest-duplicate-substring/

Star

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

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

示例 1：


输入：s = "banana"
输出："ana"

示例 2：


输入：s = "abcd"
输出：""

提示：

2 <= s.length <= 3 * 104

s 由小写英文字母组成

通过次数20,155提交次数58,474

内置hash

思路

用二分法猜测答案的长度，

题解


class Solution:
    def longestDupSubstring(self, s: str) -> str:
        n = len(s)
        l, r = 1, n-1
        ans = ""
        # 使用二分查找 猜答案
        while l <= r:
            mid = l + (r - l) // 2
            hash_set = set()
            
            for i in range(n-mid+1):
                if s[i:i+mid] in hash_set:
                    ans = s[i:i+mid]
                    break
                hash_set.add(s[i:i+mid])
            
            if len(ans) == mid:
                l = mid + 1
            else:
                r = mid - 1
        
        return ans

字符串hash

思路

思路和上面一样，只不过是手写hash。

题解


class Solution:
    def longestDupSubstring(self, s: str) -> str:
				# 经验值        
				MOD = 2 ** 64
        BASE = 13331
        # 计算 前缀 hash
        prefix = [0] * (len(s) + 1)
        power = [1] * (len(s) + 1)

        for i in range(1, len(prefix)):
            prefix[i] = (prefix[i-1] * BASE + (ord(s[i-1]) - ord("a") + 1)) % MOD
            power[i] = (power[i-1] * BASE) % MOD

        # 左闭 右开
        def get_hash(i, j):
            return (prefix[j] - prefix[i] * power[j-i] + MOD) % MOD
        
        res = ""
        l, r = 1, len(s)-1
        while l <= r:
            m = l + (r - l) // 2
            hash_set = set()
            temp = ""
            for i in range(0, len(s)-m+1):
                if get_hash(i, i+m) in hash_set:
                    print(hash_set)
                    temp = s[i:i+m]
                    break
                hash_set.add(get_hash(i, i+m))

            if temp != "":
                res = temp
                l = m + 1
            else:
                r = m - 1

        return res