查找给定哈希值的子串

难度: Hard

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：

hash(s, p, m) = (val(s[0]) * p⁰ + val(s[1]) * p¹ + ... + 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 。请你返回 s 中 第一个 长度为 k 的子串 sub ，满足 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 的子串，所以我们返回 "ee" 。

示例 2：

输入：s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
输出："fbx"
解释："fbx" 的哈希值为 hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 31²) mod 100 = 23132 mod 100 = 32 。
"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31²) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 "fbx" 。
注意，"bxz" 的哈希值也为 32 ，但是它在字符串中比 "fbx" 更晚出现。

提示：

1 <= k <= s.length <= 2 * 10⁴
1 <= power, modulo <= 10⁹
0 <= hashValue < modulo
s 只包含小写英文字母。
测试数据保证一定存在满足条件的子串。

Submission

运行时间: 92 ms

内存: 18.4 MB

class Solution:
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        # n = len(s)
        # power %= modulo
        # h = 0
        # p = 1
        
        # for  i in range(n - k + 1, n):
        #     p *= power
        #     h += (ord(s[i]) - ord('a') + 1) * p
        #     h %= modulo

        # ans = n - 1
        # for i, (in_, out_) in enumerate(zip(s[:n - k + 1][::-1], s[::-1])):
        #     h += (ord(in_) - ord('a') + 1)
        #     h %= modulo
        #     if h == hashValue:
        #         ans = n - k - i
        #     h -= (ord(out_) - ord('a') + 1) * p
        #     h *= power     
        #     h %= modulo
        # return s[ans : ans + k]
        n = len(s) ; power %= modulo
        
        mp = {chr(96+i):i for i in range(1,27)}
        
        f,g,h=[0]*(k+1),[0]*(k+1),[1]*(k+1)

        for i in range(1,k+1): h[i]=h[i-1]*power%modulo

        for i in range(0,n,k):
            for j in range(k-1,-1,-1): f[j]=(f[j+1]*power+mp[s[i+j]])%modulo

            if(f[0]==hashValue): return s[i:i+k]

            for j in range(1,min(k,n-i-k+1)): g[j]=(g[j-1]+mp[s[i+k+j-1]]*h[j-1])%modulo

            for j in range(1,min(k,n-i-k+1)):
                if((f[j]+g[j]*h[k-j])%modulo==hashValue): return s[(i+j):(i+j+k)]

Explain

此题解使用滑动窗口和哈希表来检索特定哈希值的子串。首先，代码创建一个映射mp，用于快速获取字符对应的字母表位置。使用数组f和g来计算子串的哈希值，数组h存储power的幂次模modulo的结果，用于优化计算。数组f从后向前计算当前窗口的哈希值。如果初始窗口的哈希值符合要求，直接返回该子串。否则，使用数组g从前向后递增地添加字符，并重新计算哈希值，检查每次添加后的新窗口哈希值是否符合要求。这种方法有效地避免了重复的计算，通过动态调整窗口来寻找正确的子串。

时间复杂度: O(n)

空间复杂度: O(k)

class Solution:
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        n = len(s) ; power %= modulo
        # 创建字母到数字的映射
        mp = {chr(96+i):i for i in range(1,27)}
        # 初始化数组f, g和h
        f, g, h = [0]*(k+1), [0]*(k+1), [1]*(k+1)
        # 计算power的幂次mod modulo
        for i in range(1,k+1): h[i] = h[i-1] * power % modulo
        # 主循环遍历字符串s的每k个字符
        for i in range(0,n,k):
            # 从后向前计算窗口的哈希值
            for j in range(k-1,-1,-1): f[j] = (f[j+1] * power + mp[s[i+j]]) % modulo
            # 如果初始窗口哈希值符合，返回子串
            if(f[0] == hashValue): return s[i:i+k]
            # 动态调整窗口，重新计算哈希值
            for j in range(1,min(k,n-i-k+1)): g[j] = (g[j-1] + mp[s[i+k+j-1]] * h[j-1]) % modulo
            # 检查新窗口的哈希值
            for j in range(1,min(k,n-i-k+1)):
                if((f[j] + g[j] * h[k-j]) % modulo == hashValue): return s[(i+j):(i+j+k)]

Explore

在计算哈希值时使用模运算（即使用`modulo`参数）主要是为了避免数值溢出并将哈希值控制在一个合理的范围内。由于字符串可能很长，直接计算的哈希值可能非常大，不适合直接使用。通过模运算，我们可以保证所有的哈希值都在0到`modulo-1`之间，这使得哈希值更容易管理和比较。此外，使用模运算还可以减少哈希碰撞的概率，提高算法的效率和准确性。

数组`h`用于存储`power`的幂次模`modulo`的结果的主要目的是为了优化哈希值的计算。在滑动窗口法中，我们经常需要计算新窗口的哈希值，这通常涉及到多次乘以`power`的操作。预先计算并存储`power`的幂次可以大大减少重复计算，提高整体算法的效率。这种预计算技术是一种常见的时间换空间的优化方法。

在题解中，初始窗口定义为字符串`s`中的第一个长度为`k`的子串。这个窗口从字符串的起始位置开始，长度为`k`，即字符串`s`的前`k`个字符组成的子串。算法首先计算这个初始窗口的哈希值，并与给定的`hashValue`进行比较，如果匹配，则直接返回该子串。如果不匹配，算法继续调整窗口位置，寻找其他可能的匹配子串。

在题解中，数组`f`和`g`被用于计算和更新不同窗口的哈希值，以便动态调整窗口。具体来说，`f`数组用于从当前窗口的末尾开始向前计算每个可能的子窗口的哈希值，这样做可以有效地利用已有的计算结果，从而减少重复计算。而`g`数组则用于从当前窗口的开始向后逐步添加新字符，计算扩展后的新窗口的哈希值。这两个数组的配合使用使得我们可以有效地检查每个新窗口的哈希值，从而找到符合条件的子串。