2156-查找给定哈希值的子串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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

  • hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-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 * 312) mod 100 = 23132 mod 100 = 32 。
"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 "fbx" 。
注意，"bxz" 的哈希值也为 32 ，但是它在字符串中比 "fbx" 更晚出现。

提示：

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

方法一：数学

思路与算法

对于 s 中任意长度为 k 的子串，计算该字串哈希值的时间复杂度为 O(k)。如果我们直接计算所有长度为 k 子串的哈希值，并逐个比较，则时间复杂度为 O(nk)，不符合数据范围的要求。因此我们需要优化计算不同子串哈希值的时间。

我们可以考虑两个相邻的子串 s[i..i+k-1] 与 s[i+1..i+k]，为了方便表示，我们用函数 h(i, p, m) 来表示 s[i..i+k-1] 的哈希值，即

\begin{aligned}
h(i, p, m) &= \textit{hash}(s[i..i+k-1], p, m)\
&= (\textit{val}(s[i]) \times p^0 + \textit{val}(s[i+1]) \times p^1 + \dots + \textit{val}(s[i+k-1]) \times p^{k-1}) \bmod m.
\end{aligned}

同理，我们有：

h(i + 1, p, m) = (\textit{val}(s[i+1]) \times p^0 + \textit{val}(s[i+2]) \times p^1 + \dots + \textit{val}(s[i+k]) \times p^{k-1}) \bmod m.

比较上述两式，容易发现：

h(i, p, m) = (\textit{val}(s[i]) \times p^0 + p \times h(i + 1, p, m) - \textit{val}(s[i+k]) \times p^{k}) \bmod m.

那么，如果我们预处理 p^{k} \bmod m 的值（这需要至多 O(k) 的时间复杂度），并计算出了 h(i + 1, p, m) 的取值，那么我们就可以在 O(1) 的时间内得出 h(i, p, m) 的取值。

具体而言，我们假设 s 的长度为 n，那么我们首先用 O(k) 的时间预处理 s 中最后一个长度为 k 子串的哈希值 h(n - k, p, m) 与 p^{k} \bmod m，就可以用 O(n - k) 的时间依次计算出其余每个长度为 k 子串的哈希值。我们用 pos 来维护第一个哈希值为 hashValue 的长度为 k 子串的起始下标，每当向前遍历到符合要求的子串，我们就将 pos 更新为对应的起始下标。最终，我们返回该下标起始的长度为 k 的子串作为答案。

代码

[sol1-C++]
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
class Solution {
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        int mult = 1;   // power^k mod modulo
        int n = s.size();
        int pos = -1;   // 第一个符合要求子串的起始下标
        int h = 0;   // 子串哈希值
        // 预处理计算最后一个子串的哈希值和 power^k mod modulo
        for (int i = n - 1; i >= n - k; --i) {
            h = ((long long)h * power + (s[i] - 'a' + 1)) % modulo;
            if (i != n - k) {
                mult = (long long)mult * power % modulo;
            }
        }
        if (h == hashValue) {
            pos = n - k;
        }
        // 向前计算哈希值并尝试更新下标
        for (int i = n - k - 1; i >= 0; --i) {
            h = ((h - (long long)(s[i+k] - 'a' + 1) * mult % modulo + modulo) * power + (s[i] - 'a' + 1)) % modulo;
            if (h == hashValue) {
                pos = i;
            }
        }
        return s.substr(pos, k);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        mult = 1   # power^k mod modulo
        n = len(s)
        pos = -1   # 第一个符合要求子串的起始下标
        h = 0   # 子串哈希值
        # 预处理计算最后一个子串的哈希值和 power^k mod modulo
        for i in range(n - 1, n - k - 1, -1):
            h = (h * power + (ord(s[i]) - ord('a') + 1)) % modulo
            if i != n - k:
                mult = mult * power % modulo
        if h == hashValue:
            pos = n - k
        # 向前计算哈希值并尝试更新下标
        for i in range(n - k - 1, -1, -1):
            h = ((h - (ord(s[i+k]) - ord('a') + 1) * mult % modulo + modulo) * power + (ord(s[i]) - ord('a') + 1)) % modulo
            if h == hashValue:
                pos = i
        return s[pos:pos+k]

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。即为预处理与遍历计算长度为 k 的子串的哈希值，并更新符合条件字串起始下标的时间复杂度。

  • 空间复杂度：O(1)。

 Comments
On this page
2156-查找给定哈希值的子串