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

数据结构-4.5.KMP算法(旧版上)-朴素模式匹配算法的优化

朴素模式匹配算法最坏的情况:


一.实例:

第一轮匹配失败,开始下一轮的匹配:

不断的操作,最终匹配成功:

如上述图片所述,朴素模式匹配算法会导致时间开销增加,

优化思路:主串指针不回溯,只有模式串指针回溯

主串指针不回溯:

如果上述图中?是g:

如果上述图中?不是g:

另一种情况如下:

如果在j为5时匹配失败(j为模式串的指针),那么主串中分别以第5个字符即g,第6个字符即o,第7个字符即o开头的子串都不可能与模式串匹配,但第8个字符即g开头的子串有可能与模式串匹配成功,因为第8个字符即g能与模式串第一个字符g匹配上,而且在匹配过程中只是说明了子串中第9个字符与模式串中j为5时对应的字符不匹配,并没有说明子串中第9个字符与模式串中第二个字符不匹配,接下来只需要看i对应的字符即第9个字符是否与模式串中第二个字符即o是否匹配

再下一种情况:

如果在j为4时匹配失败(j为模式串的指针),那么主串中分别以第3个字符即g,第4个字符即o,第5个字符即o开头的子串都不可能与模式串匹配,此时就需要开始判断主串中第6个字符是否与模式串中第一个字符是否匹配,但其实j为4时匹配失败已经说明主串中第6个字符不是g了,因此主串中第6个字符已经不可能与模式串中第一个字符匹配,可知该方案并不是最优解,这种方案会使得多进行一次不必要的判断,但相比朴素模式已经优化了很多:

再再下一种情况:

如果在j为3时匹配失败(j为模式串的指针),那么主串中以第四个字符即o开头的子串一定与模式串匹配失败,但此时只知道主串中第五个字符不是o,因此可以判断主串中第五个字符是否是g,以主串中第五个字符开头来重新开始与模式串的匹配,相比朴素算法也优化了很多:

再再再下一种情况:

如果在j为2时匹配失败(j为模式串的指针),那么主串中以第三个字符即g开头的子串一定与模式串匹配失败:

汇总:

对于next数组,该数组的意思是当模式串的指针j等于next数组中的某一个值时,如果发生不匹配,如j为5时不匹配,就要回到j为2这个位置;

但当j为1时发生了不匹配,j设置为0:

代码:

形参中S为主串,T为模式串,还有与T对应的next数组,i指向主串,j指向模拟串,while循环中j不为0且i指向的字符和j指向的字符不相等时才执行else语句里的j=next[j]:

与朴素算法不同的有第一个if语句中j==0和第一个else语句中的j=next[j],

现在假设主串为xgoo,模式串为google,一开始j为1,指向模拟穿里的g,i为1,指向主串里的x,

由于i和j指向的字符不匹配(不相等),根据j=next[j],会让j=next[1],此时j为0,下一轮循环时发现j为0,

++i后i为2指向主串里的g,++j后j为1指向模拟串里的g,由此就推出为什么把next[1]设为0,因为可以利用这个信息做一个特殊的判断,当j为0时就说明主串的指针i也应该往右移动了,此外当i指向的字符和j指向的字符都相等时也应该把i和j同时往后移:


相关文章:

数据结构-4.5.KMP算法(旧版上)-朴素模式匹配算法的优化

朴素模式匹配算法最坏的情况: 一.实例: 第一轮匹配失败,开始下一轮的匹配: 不断的操作,最终匹配成功: 如上述图片所述,朴素模式匹配算法会导致时间开销增加, 优化思路:主…...

STM32 QSPI接口驱动GD/W25Qxx配置简要

STM32 QSPI接口GD/W25Qxx配置简要 📝本篇会具体涉及介绍Winbond(华邦)和GD(兆易创新) NOR flash相关型号指令差异。由于网络上可以搜索到很多相关QSPI相关知识内容,不对QSPI通讯协议做深度解析。 🔖首先确保所使用的ST…...

UCI-HAR数据集深度剖析:训练仿真与可视化解读

在本篇文章中,我们将深入探讨如何使用Python对UCI人类活动识别(HAR)数据集进行分割和预处理,以及运用模型网络CNN对数据集进行训练仿真和可视化解读。 一、UCI-HAR数据集分析及介绍 UCI-HAR数据集是一个公开的数据集&#xff0c…...

牛客SQL练习详解 06:综合练习

牛客SQL练习详解 06:综合练习 SQL34 统计复旦用户8月练题情况SQL35 浙大不同难度题目的正确率SQL39 21年8月份练题总数 叮嘟!这里是小啊呜的学习课程资料整理。好记性不如烂笔头,今天也是努力进步的一天。一起加油进阶吧! SQL34 统…...

k8s apiserver高可用方案

目前官方推荐有 2 种方式部署k8s apiserver 高可用 keepalived and haproxy 部署有2种方式,一种是systemd管理的,另一种是pod形式,使用那种可以根据实际情况选择 服务部署 systemd方式 可以通过包管理工具安装,正常启动之后&…...

服务器数据恢复—硬盘坏扇区导致Linux系统服务器数据丢失的数据恢复案例

服务器数据恢复环境: 一台linux操作系统网站服务器,该服务器上部署了几十个网站,使用一块SATA硬盘。 服务器故障&原因: 服务器在工作过程中突然宕机。管理员尝试重新启动服务器失败,于是将服务器上的硬盘拆下检测…...

【多线程】多线程(12):多线程环境下使用哈希表

【多线程环境下使用哈希表(重点掌握)】 可以使用类:“ConcurrentHashMap” ★ConcurrentHashMap对比HashMap和Hashtable的优化点 1.优化了锁的粒度【最核心】 //Hashtable的加锁,就是直接给put,get等方法加上synch…...

轻量服务器和云服务器ecs哪个好用一些?

轻量服务器和云服务器ecs哪个好用一些?轻量服务器与云服务器ECS在多方面存在显著差异,对于需要高性能计算和大规模数据处理的用户来说,ECS可能是更好的选择;而对于预算有限且需求较为简单的用户来说,轻量服务器可能更为…...

【交通标志识别系统】Python+卷积神经网络算法+人工智能+深度学习+机器学习+算法模型

一、介绍 交通标志识别系统。本系统使用Python作为主要编程语言,在交通标志图像识别功能实现中,基于TensorFlow搭建卷积神经网络算法模型,通过对收集到的58种常见的交通标志图像作为数据集,进行迭代训练最后得到一个识别精度较高…...

特种设备作业叉车司机试题附答案

1.发生事故要本着"( )不放过"的原则,查明原因、分清责任、严肃处理。 A.三 B.四 C.五 答案:B 2.柴油发动机在压缩行程终了时气体的温度和压力都比汽油机( )。 A.低 B.高 C.相同 答案:B 3.柴油发动机的压缩比比汽…...

【Nginx系列】Nginx启动失败

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

2024/10/12 计组大题专训

2018: 2019: 2020: 2021:...

2024年腾讯外包面试题(微创公司)

笔试&#xff1a; 1、判断异步执行顺序 console.log(1);setTimeout(()>{Promise.resolve().then(()>{console.log(2);})console.log(3);},0);new Promise ((resolve)>{for(let i0; i<1000;i ){if(i1000){resolve();}}console.log(4);}).then(()>{console.log(5…...

nginx运行时报:No rule to make target ‘build‘, needed by ‘deault‘.Stop

项目场景&#xff1a; 部署前端项目&#xff0c;将打好的前端包&#xff0c;放到服务器上&#xff0c;运行nginx执行&#xff0c;结果nginx运行报错。 问题描述 nginx运行报以下错误&#xff1a; No rule to make target ‘build‘, needed by ‘deault‘.Stop原因分析&…...

dvwa:暴力破解、命令注入、csrf全难度详解

暴力破解 easy模式 hydra -L /usr/share/wordlists/SecLists-master/Usernames/top-usernames-shortlist.txt -P /usr/share/wordlists/SecLists-master/Passwords/500-worst-passwords.txt 192.168.72.1 http-get-form "/dvwa/vulnerabilities/brute/:username^USER^&…...

Java-学生管理系统[初阶]

这次我们来尝试使用Java实现一下"学生管理系统"&#xff0c;顾名思义&#xff0c;就是实现一个能用来管理学生各种数据的系统。在后续学习中我们将对"学生管理系统"进行两种实现&#xff1a; &#x1f4da; 学生管理系统[初阶](不带模拟登录系统) &#…...

微信小程序 详情图片预览功能实现详解

详情图片预览功能实现详解 在开发微信小程序时&#xff0c;我们经常需要实现点击商品图片进行全屏预览的功能。这不仅提升了用户体验&#xff0c;还允许用户进行保存图片、发送给朋友等操作。本文将详细介绍如何实现这一功能。 思路分析 当用户在商品详情页点击图片时&#…...

LeetCode 48 Rotate Image 解题思路和python代码

题目&#xff1a; You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and …...

余承东直播论道智能驾驶:激光雷达不可或缺,华为ADS 3.0引领安全创新

华为余承东:激光雷达,智能驾驶安全性的关键 9月29日,华为消费者业务集团CEO余承东在一场引人注目的直播中,与知名主持人马东就智能驾驶技术的最新进展进行了深入交流。在这场直播中,余承东针对激光雷达在智能驾驶中的必要性问题,发表了明确且深刻的观点,引发了业界和公众…...

51WORLD携手浙江科技大学,打造智慧校园新标杆

当前&#xff0c;国家教育数字化战略行动扎实推进&#xff0c;高等教育数字化转型步伐加快。 紧抓数字教育发展战略机遇&#xff0c;浙江科技大学联合51WORLD、正方软件股份有限公司&#xff08;简称&#xff1a;正方软件&#xff09;&#xff0c;共同研发打造浙科大孪生数智校…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...