今日题目有：

  • 最长重复子串

最长重复子串

题目描述

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

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

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

思路

为了高效地找到最长重复子串，使用二分查找 + 字符串哈希来处理

1. 二分查找

  • 设L为子串的长度，显然L的最小值是0，最大值是s.count。
  • 使用二分查找这个L，然后用哈希判断是否存在长度L的重复子串

2. 字符串哈希找重复串

字符串哈希简单来说就是把一串字符用某个哈希公式映射成一个哈希值。

这里使用滚动哈希（Rolling Hash）来计算，好处是可以在O(1)的时间内，快速更新哈希值，不用每次重新计算整个子串。

哈希公式：

如果 s[i…j] 表示 s 的一个子串： $$ \text{hash}(s[i…j]) = ( s[i] \times \text{base}^{L-1} + s[i+1] \times \text{base}^{L-2} + \dots + s[j] \times \text{base}^{0} ) \mod \text{MOD} $$ 其中：

  • s[k] 是字符的数值（ASCII - ‘a’）。
  • base 是哈希基数（通常 31 或 131）。
  • MOD 是一个大质数（如 1_000_000_007）用于防止溢出。

滚动计算：以计算新串"ana"为例子

公式： $$\text{hash}_{new} = \left( \left( \text{hash}_{\text{old}} - s[i] \times \text{base}^{L-1} \right) \times \text{base} + s[i+L] \right) \mod \text{MOD}$$

旧子串 “ban” 的哈希值： $ \text{hash}(“ban”) = 974 $

滚动更新新子串 “ana”：

  1. 去掉左侧字符 ‘b’（哈希值减少 $b \times \text{base}^{L-1}$） $$ b = 1 $$ $$ 1 \times 31^2 = 961 $$ $$ 974 - 961 = 13 $$

  2. 乘以 base，以便为新的字符腾出位置 $$ 13 \times 31 = 403 $$

  3. 加上新的字符 ‘a’（即 s[3]） $$ a = 0 $$ $$ 403 + 0 = 403 $$

最终哈希值： $ \text{hash}(“ana”) = 403 $

下面给出求"banana" 中长度 L=3 的所有哈希值的完整示例：

子串 计算方式 哈希值
"ban" 1 × 31^2 + 0 × 31^1 + 13 × 31^0 974
"ana" (974 - 961) × 31 + 0 403
"nan" (403 - 0) × 31 + 13 12506
"ana" (12506 - 13 × 961) × 31 + 0 403

Swift实现

class Solution {
    func longestDupSubstring(_ s: String) -> String {
        let n = s.count
        if n < 2 { return "" }
        let arr = Array(s)
        
        // 单哈希参数
        let base: UInt64 = 131
        let mod: UInt64 = 1_000_000_007
        
        // 预处理前缀哈希和幂数组
        // prefix[i] 表示 s[0..<i] 的哈希值
        var prefix = [UInt64](repeating: 0, count: n + 1)
        var power = [UInt64](repeating: 1, count: n + 1)
        for i in 0..<n {
            // 假设 s 全部为小写字母，将 'a' 映射为 0
            let c = UInt64(arr[i].asciiValue! - Character("a").asciiValue!)
            prefix[i + 1] = (prefix[i] * base + c) % mod
            power[i + 1] = (power[i] * base) % mod
        }
        
        // 根据预处理数组，O(1) 计算 s[i..<i+L] 的哈希值
        func getHash(i: Int, L: Int) -> UInt64 {
            return (prefix[i + L] + mod - (prefix[i] * power[L]) % mod) % mod
        }
        
        // 检查是否存在长度为 L 的重复子串
        // 如果找到重复子串，返回该子串的起始下标；否则返回 nil
        func check(_ L: Int) -> Int? {
            var seen = [UInt64: Int]()
            // 枚举所有起始位置
            for i in 0...n - L {
                let hashVal = getHash(i: i, L: L)
                if let j = seen[hashVal] {
                    // 当哈希值相同，进行一次字符串比较确认（防止哈希碰撞）
                    var equal = true
                    for k in 0..<L {
                        if arr[j + k] != arr[i + k] {
                            equal = false
                            break
                        }
                    }
                    if equal {
                        return i
                    }
                } else {
                    seen[hashVal] = i
                }
            }
            return nil
        }
        
        // 二分查找重复子串的最大长度，搜索区间 [1, n-1]
        var left = 0, right = n
        var start = -1, lengthFound = 0
        while left+1 != right {
            let mid = left + (right - left) / 2
            if let idx = check(mid) {
                // mid 长度的重复子串存在
                start = idx
                lengthFound = mid
                left = mid  // 尝试更长的
            } else {
                right = mid
            }
        }
        
        if start == -1 || lengthFound == 0 {
            return ""
        }
        return String(arr[start..<start + lengthFound])
    }
}