Hard

题目描述

给定一个长度为 k 的字符串 s（从 0 开始索引），以及整数 p 和 m，其哈希值通过以下函数计算：

hash(s, p, m) = (val(s[0]) * p^0 + val(s[1]) * p^1 + ... + val(s[k-1]) * p^(k-1)) mod m

其中 val(s[i]) 表示 s[i] 在字母表中的索引，从 val('a') = 1 到 val('z') = 26。

给定字符串 s 和整数 power、modulo、k、hashValue。返回 sub，即 s 中第一个长度为 k 且满足 hash(sub, power, modulo) == hashValue 的子字符串。

测试用例保证答案总是存在。

子字符串是字符串中连续的非空字符序列。

示例 1：

输入：s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
输出："ee"
解释："ee" 的哈希值为 hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0
"ee" 是第一个长度为 2 且哈希值为 0 的子字符串。

示例 2：

输入：s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
输出："fbx"

约束条件：

  • 1 <= k <= s.length <= 2 * 10^4
  • 1 <= power, modulo <= 10^9
  • 0 <= hashValue < modulo
  • s 只包含小写英文字母
  • 测试用例保证答案总是存在

提示：

  • 如何在迭代过程中高效更新哈希值而不是每次重新计算？
  • 使用滚动哈希方法。

解题思路

这道题要求找到第一个满足给定哈希值的长度为 k 的子字符串。关键是使用**滚动哈希（Rolling Hash）**技术来高效计算每个窗口的哈希值。

核心思路：

  1. 从右往左遍历：由于哈希函数的定义，从左往右滑动窗口时，新加入字符的幂次会不断增大，计算复杂。而从右往左遍历时，新字符总是以 power^0 = 1 的幂次加入，更容易处理。

  2. 滚动哈希更新公式：

    • 当窗口右移时（从右往左看是左移），移除最高位字符，所有字符的幂次减1
    • 公式：newHash = (oldHash - val(removed) * power^(k-1)) * power + val(added)

  3. 预计算幂次：预先计算 power^(k-1) mod modulo，避免重复计算。

  4. 逆向思维：由于我们从右往左遍历，需要记录最后一个满足条件的位置，这样就能找到"第一个"（最左边的）满足条件的子字符串。

算法步骤：

  1. 先计算字符串末尾长度为 k 的子字符串的哈希值
  2. 从右往左滑动窗口，使用滚动哈希更新哈希值
  3. 记录每个满足条件的位置，最终返回最左边的结果

时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        int n = s.length();
        long long hash = 0;
        long long pk = 1;
        
        // Calculate power^(k-1) mod modulo
        for (int i = 0; i < k - 1; i++) {
            pk = (pk * power) % modulo;
        }
        
        // Calculate hash of last k characters
        for (int i = n - k; i < n; i++) {
            hash = (hash * power + (s[i] - 'a' + 1)) % modulo;
        }
        
        int result = n - k; // Start from the last possible position
        if (hash == hashValue) {
            // No need to continue if the last substring matches
        }
        
        // Rolling hash from right to left
        for (int i = n - k - 1; i >= 0; i--) {
            // Remove the rightmost character and add the new leftmost character
            hash = (hash - ((long long)(s[i + k] - 'a' + 1) * pk) % modulo + modulo) % modulo;
            hash = (hash * power + (s[i] - 'a' + 1)) % modulo;
            
            if (hash == hashValue) {
                result = i;
            }
        }
        
        return s.substr(result, k);
    }
};

class Solution:
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        n = len(s)
        hash_val = 0
        pk = pow(power, k - 1, modulo)
        
        # Calculate hash of last k characters
        for i in range(n - k, n):
            hash_val = (hash_val * power + (ord(s[i]) - ord('a') + 1)) % modulo
        
        result = n - k  # Start from the last possible position
        if hash_val == hashValue:
            pass  # Already found at the end
        
        # Rolling hash from right to left
        for i in range(n - k - 1, -1, -1):
            # Remove the rightmost character and add the new leftmost character
            hash_val = (hash_val - (ord(s[i + k]) - ord('a') + 1) * pk) % modulo
            hash_val = (hash_val * power + (ord(s[i]) - ord('a') + 1)) % modulo
            
            if hash_val == hashValue:
                result = i
        
        return s[result:result + k]

public class Solution {
    public string SubStrHash(string s, int power, int modulo, int k, int hashValue) {
        int n = s.Length;
        long hash = 0;
        long pk = 1;
        
        // Calculate power^(k-1) mod modulo
        for (int i = 0; i < k - 1; i++) {
            pk = (pk * power) % modulo;
        }
        
        // Calculate hash of last k characters
        for (int i = n - k; i < n; i++) {
            hash = (hash * power + (s[i] - 'a' + 1)) % modulo;
        }
        
        int result = n - k; // Start from the last possible position
        if (hash == hashValue) {
            // No need to continue if the last substring matches
        }
        
        // Rolling hash from right to left
        for (int i = n - k - 1; i >= 0; i--) {
            // Remove the rightmost character and add the new leftmost character
            hash = (hash - ((long)(s[i + k] - 'a' + 1) * pk) % modulo + modulo) % modulo;
            hash = (hash * power + (s[i] - 'a' + 1)) % modulo;
            
            if (hash == hashValue) {
                result = i;
            }
        }
        
        return s.Substring(result, k);
    }
}

var subStrHash = function(s, power, modulo, k, hashValue) {
    const n = s.length;
    let hash = 0;
    let powerK = 1;
    
    // Calculate power^(k-1) mod modulo
    for (let i = 0; i < k - 1; i++) {
        powerK = (powerK * power) % modulo;
    }
    
    // Calculate hash from right to left starting from the last k characters
    for (let i = n - 1; i >= n - k; i--) {
        const val = s.charCodeAt(i) - 96; // 'a' = 1, 'b' = 2, etc.
        hash = (hash * power + val) % modulo;
    }
    
    if (hash === hashValue) {
        return s.substring(n - k, n);
    }
    
    // Slide window from right to left
    for (let i = n - k - 1; i >= 0; i--) {
        const newVal = s.charCodeAt(i) - 96;
        const oldVal = s.charCodeAt(i + k) - 96;
        
        // Remove the rightmost character and add new leftmost character
        hash = (hash - (oldVal * powerK) % modulo + modulo) % modulo;
        hash = (hash * power + newVal) % modulo;
        
        if (hash === hashValue) {
            return s.substring(i, i + k);
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串一次，每次更新哈希值为常数时间
空间复杂度O(1)只使用常数额外空间存储哈希值和相关变量

相关题目