查找给定哈希值的子串

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

给定整数 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 只包含小写英文字母。
测试数据保证一定存在满足条件的子串。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: string subStrHash(string s, int power, int modulo, int k, int hashValue) { } };

java 解法, 执行用时: 8 ms, 内存消耗: 43.2 MB, 提交时间: 2023-07-01 13:50:30

class Solution {
	public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
		char[] cs = s.toCharArray();
		int len = cs.length;
		long hash = 0;
		long pp = 1;
		for (int i = len - k; i < len; i++) {
			hash += (cs[i] - 'a' + 1) * pp;
			hash %= modulo;
			pp = pp * power % modulo;
		}
		int ans = len - k;
		int p = len - k - 1;
		while (p >= 0) {
			hash *= power;
			hash -= (cs[p + k] - 'a' + 1) * pp % modulo;
			hash += (cs[p] - 'a' + 1) % modulo;
			hash = (hash + modulo) % modulo;
			if (hash == hashValue) {
				ans = p;
			}
			p--;
		}
		return new String(cs, ans, k);
	}

}

java 解法, 执行用时: 1975 ms, 内存消耗: 43.3 MB, 提交时间: 2023-07-01 13:50:06

class Solution {
        public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
            long[] pows = new long[k];
            pows[0] = 1;
            for (int i = 1; i < k; i++) {
                pows[i] = pows[i - 1] * power % modulo;
            }

            for (int i = 0; i <= s.length() - k; i++) {
                String subStr = s.substring(i, i + k);
                if (val(subStr, pows, modulo) == hashValue) {
                    return subStr;
                }
            }
            return "";
        }

        private int val(String subStr, long[] pows, int modulo) {
            long res = 0;
            for (int i = 0; i < subStr.length(); i++) {
                res += (subStr.charAt(i) - 'a' + 1) * pows[i];
                res %= modulo;
            }
            return (int) (res % modulo);
        }
}

cpp 解法, 执行用时: 16 ms, 内存消耗: 10 MB, 提交时间: 2023-07-01 13:49:36

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);
    }
};

python3 解法, 执行用时: 180 ms, 内存消耗: 16.3 MB, 提交时间: 2023-07-01 13:49:22

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]

golang 解法, 执行用时: 8 ms, 内存消耗: 5.3 MB, 提交时间: 2023-07-01 13:49:03

func subStrHash(s string, power, mod, k, hashValue int) (ans string) {
	hash, p := 0, 1
	i, n := len(s)-1, len(s)
	for ; i >= n-k; i-- {
		hash = (hash*power + int(s[i]&31)) % mod // 用秦九韶算法计算 s[n-k:] 的哈希值
		p = p * power % mod
	}
	if hash == hashValue {
		ans = s[n-k:]
	}
	for ; i >= 0; i-- { // 倒着向前滑动窗口
		hash = (hash*power + int(s[i]&31) + mod - p*int(s[i+k]&31)%mod) % mod // 计算新哈希值
		if hash == hashValue {
			ans = s[i : i+k]
		}
	}
	return
}

上一题

下一题

详情