数据结构(4.4)——求next数组

next数组的作用:当模式串的第j个字符失配时,从模式串的第next[j]的继续往后匹配

求模式串的next数组(手算)

next[1]

任何模式串都一样,第一个字符不匹配时,只能匹配下一个子串,因此,往后,next[1]都无脑写0

next[2] 

 任何模式串都一样,第二个字符不匹配时,只能匹配模式串的第1个字符,因此,往后,next[1]都无脑写1

next[3]  

在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少

 

next[4]  

在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少

next[5]

在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少

next[6]

在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少

 

总结

next[1]都无脑写0 

next[2]都无脑写1

其他next:在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少

例题:

求模式串:ababaa的next数组

//求next[1]

??????->??????//i=1->i=2

ababaa-> ababaa //j=0,第一个字符匹配失败,只能匹配下一个子串,++i,++j

next[1]=0;

//求next[2]

a?????->a??????  //i=2

ababaa->  ababaa  //j=1//第一个字符匹配成功,第二个字符匹配失败,i不动,j后退一步

next[2]=1;

//求next[3]

ab????->ab????//i=3

ababaa->    ababaa//第三个字符匹配失败,模式串后退两步,j指向1,j=1

next[3]=1

//求next[4]

aba???->aba???//i=4

ababaa->    ababaa//第四个字符匹配失败,模式串后退,第一个字符a和主串第三个字符a匹配,j指向2,j=2

next[4]=2

//求next[5]

abab??->abab??//i=5

ababaa->    ababaa//第五个字符匹配失败,模式串后退,字符串ab和主串第二个子串ab匹配,j指向3,j=3

next[5]=3

 

//求next[6]

ababa?->ababa?//i=6

ababaa->    ababaa//第六个字符匹配失败,模式串后退,字符串ab和主串第二个子串aba匹配,j指向4,j=4

next[6]=4

 例题2同理:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/377334.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

51单片机6(P0P1P2P3结构框架图)

一、GPIO结构框架图与工作原理 1、接下来我们介绍一下这个GPIO结构框图和工作原理,我们使用51单片机的GPIO分为了P0,P1,P2,P3这四组端口,下面我们就分别来介绍这四组端口它的一个内部结构,只有了解了内部的…

排序相关算法--3.选择排序

之前涉及的堆排序就是选择排序的一种,先进行选择。 基本选择排序: 最简单,也是最没用的排序算法,时间复杂度高并且还是不稳定的排序方法,项目中很少会用。 过程: 在一个长度为 N 的无序数组中,…

Python使用策略模式和openpyxl库创建Excel文件并追加内容

from openpyxl import load_workbook# 数据数组 data [[1, 2, 3],[4, 5, 6],[7, 8, 9] ]# 打开现有的 Excel 文件 excel_file sheetApend_example.xlsx wb load_workbook(excel_file)# 选择要追加数据的工作表 sheet_name test_Sheet2 # 指定要追加数据的工作表名称 sheet…

最值得推荐的10款Windows软件!

AI视频生成:小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频播放量破百万https://aitools.jurilu.com/1.音乐播放器——Dopamine Dopamine是一款音乐播放器,设计简洁美观。它支持多种音频格式,包括wav、mp3、ogg…

爬虫管理解决方案:让数据收集变得高效且合规

一、为何数据收集的效率与合规性同等重要? 随着大数据技术的飞速发展,数据收集已成为企业决策与市场洞察的核心驱动力。然而,在信息海洋中精准捕捞的同时,如何确保这一过程既高效又不触碰法律的红线,是每个数据实践者…

“金山-讯飞”杯2024年武汉理工大学程序设计竞赛 A. Mobiusp败走***(思维题-点双连通分量、连通性)

题目 思路来源 官方题解 题解 手玩发现,能换的话,当且仅当.和1在一个环里,而这就是点双连通分量 所以最优策略是先把.换到(x,y)的位置,然后判断.和1在不在一个环里 也就是: 1. 判断删掉1时,.和(x,y)联…

C++客户端Qt开发——信号和槽

三、信号和槽 1.信号和槽概述 在Qt中,用户和控件的每次交互过程称为一个事件。比如"用户点击按钮”是一个事件,"用户关闭窗口”也是一个事件。每个事件都会发出一个信号,例如用户点击按钮会发出"按钮被点击"的信号&…

基于JavaEE 的影视创作论坛的设计与实现

点击下载源码 基于Javaee的影视创作论坛的设计与实现 摘 要 随着时代的发展,互联网的出现,给传统影视行业带来的最大便利就是,方便了影视从业人员以及爱好者的交流和互动,而为用户提供一个书写影评,阅读影评以及回复…

Centos7 安装Redis6.2.6 gcc报错问题解决

Redis 报错信息 make: *** [all] 错误 2 安装gcc 修改yum源,在安装更新rpm包时获得比较理想的速度,走阿里云镜像通道 发现报错信息如下: 正在解析主机 mirrors.aliyun.com (mirrors.aliyun.com)… 失败:未知的名称或服务。 wget: 无法解析主机地址 “mi…

9.5 栅格图层符号化多波段彩色渲染

文章目录 前言多波段彩色渲染QGis设置为多波段彩色二次开发代码实现多波段彩色 总结 前言 介绍栅格图层数据渲染之多波段彩色渲染说明:文章中的示例代码均来自开源项目qgis_cpp_api_apps 多波段彩色渲染 以“3420C_2010_327_RGB_LATLNG.tif”数据为例&#xff0c…

【C++】初识C++(下)

前言 本篇博客继续总结一下C入门的一些小知识 💓 个人主页:小张同学zkf ⏩ 文章专栏:C 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章 ​ 目录 1.引用 1.1引用的概念 1.2const引用 1.3指针和引用的…

无损音乐播放器推荐:Audirvana for Mac 中文激活版

udirvana 是一款高品质的音乐播放软件,专为Mac操作系统设计。它被设计来提供音频播放的最高标准,支持多种音频格式,包括高达32位/192kHz的高分辨率音频。Audirvana Plus 是其高级版本,提供了更多的功能和优化,例如音频…

Redis 主从复制,哨兵与集群

目录 一.redis主从复制 1.redis 主从复制架构 2.主从复制特点 3.主从复制的基本原理 4.命令行配置 5.实现主从复制 6.删除主从复制 7.主从复制故障恢复 8.主从复制完整过程 9.主从同步优化配置 二.哨兵模式(Sentinel) 1.主要组件和概念 2.哨…

LabVIEW电容器充放电监测系统

概述 为了对车用超级电容器的特性进行研究,确保其在工作时稳定可靠并有效发挥性能优势,设计了一套车用超级电容器充放电监测系统。该系统通过利用传感器、USB数据采集卡、可调直流稳压电源、电子负载以及信号调理电路,完成对各信号的采集和超…

数据分组还在手忙脚乱?Python groupby一招搞定,效率翻倍!

目录 1、初识groupby:基础用法 🐍 1.1 groupby函数简介 1.2 准备数据与分组 2、按键分组 📊 2.1 使用lambda表达式 2.2 自定义key函数 3、连续元素分组 🔗 3.1 不连续元素处理 3.2 连续性与排序 4、组合其他itertools模…

基于香橙派 AIpro设计的医院人脸红外测温系统(从0开始开发)

文章目录 一、前言二、主控板介绍三、搭建开发环境3.1 准备需要的配件3.2 开发板实物图3.3 下载开发板资料3.4 下载系统烧写工具3.5 设置开发板启动模式3.6 启动系统3.7 SSH远程登录系统3.8 安装xdrp工具3.9 Window远程登录3.10 取消自动休眠 四、安装Qt开发环境4.1 安装qtcrea…

Ubuntu系统安装mysql之后进行远程连接

1.首先要配置数据库允许进行远程连接 1.1 打开MySQL配置文件 /etc/mysql/mysql.conf.d/mysqld.cnf sudo vim /etc/mysql/mysql.conf.d/mysqld.cnf1.2 修改 bind-address 行 #按i进入插入模式 bind-address 0.0.0.0 #按 Esc 键退出插入模式。 #输入:wq 然后按 Enter 保存并退…

MySQL第八次作业

一、备份与恢复作业: 创库,建表: CREATE DATABASE booksDB; use booksDB; CREATE TABLE books ( bk_id INT NOT NULL PRIMARY KEY, bk_title VARCHAR(50) NOT NULL, copyright YEAR NOT NULL ); CREATE TABLE authors …

在uniapp中如何使用地图

1&#xff0c;技术选择 最好是使用webview html形式加载&#xff0c;避免打包app时的地图加载问题 2&#xff0c;webview使用 使用webview必须按照官方文档,官网地址&#xff1a;https://uniapp.dcloud.net.cn/component/web-view.html <template><view><!…

MATLAB激光通信和-积消息传递算法(Python图形模型算法)模拟调制

&#x1f3af;要点 &#x1f3af;概率论和图论数学形式和图结构 | &#x1f3af;数学形式、图结构和代码验证贝叶斯分类器算法&#xff1a;&#x1f58a;多类型&#xff1a;朴素贝叶斯&#xff0c;求和朴素贝叶斯、高斯朴素贝叶斯、树增强贝叶斯、贝叶斯网络增强贝叶斯和半朴素…