Rabin Karp 字符匹配算法

Rabin Karp 字符匹配算法

相关题目：
187. 重复的DNA序列
28. 找出字符串中第一个匹配项的下标

class FindRepeatedDnaSequences:"""187. 重复的DNA序列https://leetcode.cn/problems/repeated-dna-sequences/description/"""def solution(self, s: str) -> List[str]:nums = [0] * len(s)for i in range(len(nums)):if s[i] == 'A':nums[i] = 0elif s[i] == 'G':nums[i] = 1elif s[i] == 'C':nums[i] = 2elif s[i] == 'T':nums[i] = 3# 记录重复出现的哈希值seen = set()# 记录重复出现的字符串结果res = set()# 数字位数L = 10# 进制R = 4# 存储 R^(L - 1) 的结果RL = R ** (L - 1)# 维护滑动窗口中字符串的哈希值windowHash = 0# 滑动窗口代码框架，时间 O(N)left, right = 0, 0while right < len(nums):# 扩大窗口，移入字符，并维护窗口哈希值（在最低位添加数字）windowHash = R * windowHash + nums[right]right += 1# 当子串的长度达到要求if right - left == L:# 根据哈希值判断是否曾经出现过相同的子串if windowHash in seen:# 当前窗口中的子串是重复出现的res.add(s[left:right])else:# 当前窗口中的子串之前没有出现过，记下来seen.add(windowHash)# 缩小窗口，移出字符，并维护窗口哈希值（删除最高位数字）windowHash -= nums[left] * RLleft += 1# 转化成题目要求的 List 类型return list(res)

class StrStr:"""28. 找出字符串中第一个匹配项的下标https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/"""def solution(self, haystack: str, needle: str) -> int:# 文本串txt = haystack# 模式串pat = needle# 需要寻找的子串长度为模式串 pat 的长度L = len(pat)# 仅处理 ASCII 码字符串，可以理解为 256 进制的数字R = 256# 存储 R^(L - 1) 的结果RL = R ** (L - 1)# 维护滑动窗口中字符串的哈希值windowHash = 0# 计算模式串的哈希值patHash = 0for i in range(len(pat)):patHash = R * patHash + ord(pat[i])# 滑动窗口代码框架left, right = 0, 0while right < len(txt):# 扩大窗口，移入字符（在最低位添加数字）windowHash = R * windowHash + ord(txt[right])right += 1# 当子串的长度达到要求if right - left == L:# 根据哈希值判断窗口中的子串是否匹配模式串 patif patHash == windowHash:# 找到模式串print("找到模式串，起始索引为", left)return left# 缩小窗口，移出字符（删除最高位数字）windowHash = windowHash - ord(txt[left]) * RLleft += 1# 没有找到模式串return -1