为公司建设网站的意义,哪个平台开网店不收费,网站前台代码,蒲江网站建设文章目录1. 题目2. 解题1. 题目
给定整数 p 和 m #xff0c;一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算#xff1a; hash(s,p,m)(val(s[0])∗p0val(s[1])∗p1...val(s[k−1])∗pk−1)modmhash(s,p,m) (val(s[0])*p^0 val(s[1])*p^1...val(s[k-1])…
文章目录1. 题目2. 解题1. 题目
给定整数 p 和 m 一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算 hash(s,p,m)(val(s[0])∗p0val(s[1])∗p1...val(s[k−1])∗pk−1)modmhash(s,p,m) (val(s[0])*p^0 val(s[1])*p^1...val(s[k-1])*p^{k-1}) \quad mod \quad mhash(s,p,m)(val(s[0])∗p0val(s[1])∗p1...val(s[k−1])∗pk−1)modm
其中 val(s[i]) 表示 s[i] 在字母表中的下标从 val(a) 1 到 val(z) 26 。
给你一个字符串 s 和整数 powermodulok 和 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 * 10^4
1 power, modulo 10^9
0 hashValue modulo
s 只包含小写英文字母。
测试数据保证一定 存在 满足条件的子串。来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-substring-with-given-hash-value 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
逆向做字符串哈希然后用大小为 k 的滑动窗口向前滑动每次以 O(1) 的时间复杂度获取窗口内的字符串哈希值
from functools import lru_cache
class Solution:def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) - str:lru_cache()def powk(p, k, mod): # 快速幂ans 1product pwhile k:if k1:ans (ans*product)%modproduct * productproduct % modk 1return ans%modhashval 0n len(s)for i in range(n-1, n-k, -1): # k-1个字符的哈希值hashval hashval*power (ord(s[i])-ord(a)1)hashval % modulopos -1for i in range(n-k, -1, -1): # 滑窗获取以后的 k 个字符的哈希值hashval hashval*power (ord(s[i])-ord(a)1)hashval % moduloif hashval hashValue:pos ihashval (hashval-(ord(s[ik-1])-ord(a)1)*powk(power, k-1, modulo)26*modulo)%moduloreturn if pos-1 else s[pos:posk] 256 ms 15.2 MB Python3 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
