当前位置: 首页 > news >正文

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

相关文章:

Rabin Karp 字符匹配算法

Rabin Karp 字符匹配算法 相关题目&#xff1a; 187. 重复的DNA序列 28. 找出字符串中第一个匹配项的下标 class FindRepeatedDnaSequences:"""187. 重复的DNA序列https://leetcode.cn/problems/repeated-dna-sequences/description/"""def sol…...

星宿UI2.51资源付费变现小程序 支持流量主广告投放

目前&#xff0c;最新版的星宿UI是2.51版本。要搭建星宿UI&#xff0c;您需要准备备用域名、服务器和微信小程序账号。星宿UI提供了多项功能&#xff0c;包括文章展示、文章分类、资源链接下载和轮播图等。此外&#xff0c;还支持直接下载附件功能。这些功能使得星宿UI非常适合…...

Telnet 测试 UDP 端口?

Telnet 并不支持 UDP 端口的测试&#xff0c;可以使用 nc 命令来进行测试。nc 命令两种都支持&#xff1a; TCP # nc -z -v -u [hostname/IP address] [port number] # nc -z -v 192.168.10.12 22 Connection to 192.118.20.95 22 port [tcp/ssh] succeeded! UDP # nc -z -v…...

【论文复现】常见问题

1. 提取出错 首先检查嵌入时的像素值是否越界&#xff08;0-255&#xff09;&#xff0c;如果越界则在提取的时候无法正确提取嵌入的时候注意整数除法和浮点数除法向下取整结果不一样&#xff0c;floor(int(10)/16)1&#xff0c;floor(double(10)/16)0 2. 常用代码部分 1.生…...

Uniapp开发 购物商城源码 在线电商商城源码 适配移动终端项目及各小程序

lilishop电商商城系统 商城移动端&#xff0c;使用Uniapp开发&#xff0c;可编译为所有移动终端项目及各小程序 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/88487579 源码下载2&#xff1a;关注我留言...

xml schema中的sequence的含义

https://www.w3.org/TR/xmlschema-1/#element-sequence xml schema中的sequence的含义&#xff1a;包含的元素必须按规定的顺序出现。通过属性maxOccurs和minOccurs可以定义最多、最少出现的次数。最多可以定义不限制次数&#xff0c;最少可以定义0次。默认是最少出现1次&…...

详解 KEIL C51 软件的使用·建立工程

单片机要运行,就必须将程序代码下载到程序存储器内部,但是在写进单片机之前要先将你写 的程序转换成*.hex 或*.bin 的文件.不同系列的单片机都有不同的软件对其进行编绎,而 keil Cx51 是德国开发的一个专为 51 系列单片机提供的软件开发平台,基本上现在的所有 51 系列内核的单片…...

2023年03月 Python(五级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 已知一个列表lst = [2,3,4,5,6],lst.append(20),print(lst)的结果是?( )(2分) A.[10,2,3,4,5,6,20] B.[20,2,10,3,4,5,6] C.[2,3,4,5,6,20] D.[2,3,4,5,6,10,20] 答案:C 第2…...

nginx 代理服务时遇到的问题

一 nginx代理多个服务&#xff0c;且服务之间需要相互通信 多个服务运行在docker容器中&#xff0c;nginx同样在docker容器中 比如前端服务需要请求后端服务&#xff0c;用户请求服务器80或者443 &#xff0c;nginx代理请求到前端服务&#xff0c;前端服务业务请求到后端服务…...

利用共享台球室小程序系统提升用户体验

随着移动互联网的普及&#xff0c;越来越多的用户倾向于使用手机应用来解决生活中的问题。共享台球室作为一个结合了传统与现代元素的项目&#xff0c;也需要借助移动小程序的力量来提升用户体验。本文将探讨如何利用共享台球室小程序系统提升用户体验。 一、提供便捷的服务 …...

U-Mail海外邮件中继帮您解决企业邮件退信难题

过去一年&#xff0c;国内外形势严峻复杂&#xff0c;但中国外贸顶住压力、爬坡过坎&#xff0c;进出口规模冲破40万亿元大关&#xff0c;高达42万亿元人民币&#xff0c;中国连续6年位居货物贸易第一大国。随着我国疫情防控措进入新阶段&#xff0c;“拼经济”正在成为各地的一…...

ImageJ灰度值量化分析 实用技巧——免疫组化分析(定量分析篇)

在临床病理诊断中&#xff0c; 免疫组织化学( Immunohistochemistry, IHC) 是一种很重要的技术和手段。 免疫组化标记时细胞阳性着色程度取决于抗原含量、分布密度和标记方法及其敏感性。 一般而言&#xff0c;抗原含量越多&#xff0c;分布密度越高&#xff0c;阳性结果显色…...

了解STM32看门狗定时器的工作原理和原则

STM32 系列微控制器的看门狗定时器 (Watchdog Timer&#xff0c;WWDG) 是一种重要的硬件资源&#xff0c;用于检测系统的异常状态&#xff0c;并在发生异常时执行特定的操作&#xff0c;以确保系统能够正常运行。在本文中&#xff0c;我将详细介绍 STM32 看门狗定时器的工作原理…...

【2014年数据结构真题】

41. (13分&#xff09;二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。 给定一棵二叉树T,采用二叉链表存储&#xff0c;结点结构如下&#xff1a; 其中叶结点的weight域保存该结点的非负权值。 设root为指向T的根结点的指针&#xff0c; 请设计求T 的WPL…...

PostgreSQL基本操作

目录 1.源码安装PostgreSQL 1.1.前置条件&#xff08;root下操作&#xff09; 1.1.1.卸载yum安装的postgresql 1.1.2.创建postgres用户 1.1.3.安装部分依赖 1.1.4.源码安装uuid 1.2.安装PostgreSQL 1.2.1.使用postgres用户管理PostgreSQL 1.2.2.下载解压postgres12源码…...

hadoop 大数据环境配置 ssh免密登录 centos配置免密登录 hadoop(四)

1. 找到.ssh文件夹 cd ~ # 在.ssh文件夹下生成 # cd .ssh 2. 生成私钥公钥命令&#xff1a; ssh-keygen -t rsa3. 发送到需要免密机器&#xff1a; # hadoop23 是我做了配置。在host配置得机器ip和名称得映射 ssh-copy-id hadoop23 4. 成功...

Django 的国际化与本地化详解

概要 随着全球化的发展&#xff0c;为 Web 应用提供多语言支持变得日益重要。Django 作为一个功能强大的 Web 框架&#xff0c;提供了一套完整的国际化&#xff08;i18n&#xff09;和本地化&#xff08;l10n&#xff09;工具&#xff0c;使得开发多语言应用变得简单。本文将详…...

Java19新增特性

前言 前面的文章&#xff0c;我们对Java9、Java10、Java11、Java12 、Java13、Java14、Java15、Java16、Java17、Java18 的特性进行了介绍&#xff0c;对应的文章如下 Java9新增特性 Java10新增特性 Java11新增特性 Java12新增特性 Java13新增特性 Java14新增特性 Java15新增特…...

[文件读取]metinfo_6.0.0 任意文件读取漏洞复现

1.1漏洞描述 漏洞编号--漏洞类型文件读取漏洞等级⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐漏洞环境windows漏洞名称MetInfo 6.0.0 任意文件读取漏洞 MetInfo 是一套使用PHP 和MySQL 开发的内容管理系统。MetInfo 6.0.0 版本中的 /app/system/include/module/old_thumb.class.php 文件存在任意文件…...

[量化投资-学习笔记015]Python+TDengine从零开始搭建量化分析平台-量化知识点汇总

之前的章节介绍了多个技术分析指标&#xff0c;以下进行一个简单的总结。 看过之前章节的同学就可以不用打开了。 技术指标 MAEMAMACDCCIATRKDJ MA 最基础的技术指标&#xff0c;对一段周期内的收盘价进行简单平均&#xff0c;是一切指标的基础。 def calc_ma(period,ma):ma_…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...