数据结构(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.mfbz.cn/a/801391.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python的日期和时间

时间与日期 基础知识(python的时间表示方法) 时间戳 时间戳是一个用于表示特定时间点的方式,它表示自1970年1月1日00:00:00 UTC(协调世界时)以来经过的秒数。时间戳通常用于编程中,因为它提供了一种简单的方…

树结构添加分组,向上向下添加同级,添加子级

树结构添加分组&#xff0c;向上向下添加同级&#xff0c;添加子级 效果代码实现页面js 效果 代码实现 页面 <el-tree :data"treeData" :props"defaultProps" :expand-on-click-node"false":filter-node-method"filterNode" :ref&…

实战:功能强大齐全BBS论坛项目Echo简介

项目简介 Echo 是一套前后端不分离的开源社区系统&#xff0c;基于目前主流 Java Web 技术栈&#xff08;SpringBoot MyBatis MySQL Redis Kafka Elasticsearch Spring Security ...&#xff09;&#xff0c;并提供详细的开发文档和配套教程。包含帖子、评论、私信、系…

QT官方modbus_slave例子嵌入到界面

1.打开QT官方modbus_slave的例子 根据提示略微配置一下编译选项&#xff0c;就可以正常运行。 2.新将一个项目包含这个例子 这个例子非常简单&#xff0c;就是在默认的mainwindow上给个按钮&#xff0c;点击按钮调用这个例子的界面。 3.修改*.pro文件 serialport serialbus …

腾讯解禁 QQ 极速版,且看我收集的最全 QQ 各类版本

因为利益关系&#xff0c;腾讯早就限制QQ极速版的登录了&#xff0c;近日居然解除限制了&#xff0c;面对越来越臃肿的QQ&#xff0c;我给大伙准备了几十个版本的QQ&#xff0c;总有一个适合你。 QQ版本合集 给大伙们收集了QQ版本合集&#xff0c;分别有历史版本、精简版本、内…

第59期|GPTSecurity周报

GPTSecurity是一个涵盖了前沿学术研究和实践经验分享的社区&#xff0c;集成了生成预训练Transformer&#xff08;GPT&#xff09;、人工智能生成内容&#xff08;AIGC&#xff09;以及大语言模型&#xff08;LLM&#xff09;等安全领域应用的知识。在这里&#xff0c;您可以找…

动手学深度学习——3.多层感知机

1.线性模型 线性模型可能出错 例如&#xff0c;线性意味着单调假设&#xff1a; 任何特征的增大都会导致模型输出的增大&#xff08;如果对应的权重为正&#xff09;&#xff0c; 或者导致模型输出的减小&#xff08;如果对应的权重为负&#xff09;。 有时这是有道理的。 例…

【Java--数据结构】队列与栈的相互成就

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 目录 用队列实现栈 用栈实现队列 用队列实现栈 oj链接 一个队列是无法实现栈的 入栈push&#xff1a;把数据放到不为空的队列当中。 注意&#xff1a;第一次入栈时&…

手写new

手写new new是什么执行new会发生什么实现new new是什么 new 操作符是可以创建一个用户定义的对象的实例或具有构造函数的内置对象的实例 function Car (make, model, year) {this.make makethis.model modelthis.year year } Car.prototype.running function () {return …

R语言极值分析:GEV与GPD模型与MCMC的海洋观测数据极值模拟可视化研究

全文链接&#xff1a;https://tecdat.cn/?p37007 原文出处&#xff1a;拓端数据部落公众号 在海洋科学领域&#xff0c;极端天气和海洋事件如极端海浪、风暴潮和海啸等&#xff0c;对沿海社区、基础设施及生态环境构成了重大威胁。准确预测和评估这些极端事件的强度和频率&a…

Golang中读写锁的底层实现

目录 Sync.RWMutex 背景与机制 接口简单介绍 sync.RWMutex 数据结构 读锁流程 RLock RUnlock RWMutex.rUnlockSlow 写锁流程 Lock Unlock Sync.RWMutex 背景与机制 从逻辑上&#xff0c;可以把 RWMutex 理解为一把读锁加一把写锁&#xff1b; 写锁具有严格的排他性&…

Qt程序图标更改以及程序打包

Qt程序图标更改以及程序打包 1 windows1.1 cmake1.1.1 修改.exe程序图标1.1.2 修改显示页面左上角图标 1.2 qmake1.2.1 修改.exe程序图标1.2.2 修改显示页面左上角图标 2 程序打包2.1 MinGW2.2 Visual Studio 3 参考链接 1 windows 1.1 cmake 1.1.1 修改.exe程序图标 获得一个…

【Linux】进程控制的详细介绍

前言 在此之前&#xff0c;我们学过进程的概念&#xff0c;进程的状态&#xff0c;进程地址空间等一系列进程相关的问题。本章我们继续学习进程&#xff0c;我们要来学习一下进程的控制&#xff0c;关于进程等待&#xff0c;等问题。 目录 1.再次认识Fork函数1.1 fork()之后操…

搜集日志。

logstash 负责&#xff1a; 接收数据 input — 解析过滤并转换数据 filter(此插件可选) — 输出数据 output input — decode — filter — encode — output elasticsearch 查询和保存数据 Elasticsearch 去中心化集群 Data node 消耗大量 CPU、内存和 I/O 资源 分担一部分…

数据结构进阶:使用链表实现栈和队列详解与示例(C, C#, C++)

文章目录 1、 栈与队列简介栈&#xff08;Stack&#xff09;队列&#xff08;Queue&#xff09; 2、使用链表实现栈C语言实现C#语言实现C语言实现 3、使用链表实现队列C语言实现C#语言实现C语言实现 4、链表实现栈和队列的性能分析时间复杂度空间复杂度性能特点与其他实现的比较…

启动yarn后,其他节点没有NodeManager

写在前面&#xff1a; 这个问题虽然折磨了我两天&#xff0c;但是原因特别蠢&#xff0c;可能与各位不一定一样&#xff0c;我是因为ResourceManager的节点的"/etc/hadoop/workers"文件没有配置好&#xff08;没有配hadoop102和hadoop104&#xff09;&#xff0c;但排…

MySQL日期和时间相关函数

目录 1. 获取当前时间和日期 2. 获取当前日期 3. 获取当前时间 4. 获取单独的年/月/日/时/分/秒 5. 添加时间间隔 date_add ( ) 6. 格式化日期 date_format ( ) 7. 字符串转日期 str_to_date () 8. 第几天 dayofxx 9. 当月最后一天 last_day ( ) 10. 日期差 datedif…

Java中的线程同步

为什么要实现线程同步 线程的同步是为了保证多个线程按照特定的顺序、协调地访问共享资源&#xff0c;避免数据不一致和竞争条件等问题。 线程同步的方式 1.synchronized关键字 &#xff08;1&#xff09;同步方法 public synchronized void save(){} 注&#xff1a; syn…

网络编程+文件上传操作的理解

前言&#xff1a; 概述:在网络通信协议下,不同计算机上运行的程序,进行数据传输 比如:通信,视频通话,网游,邮件等 只要是计算机之间通过网络进行数据传输,就有网络编程的存在 &#xff08;下面单纯是在Java基础中了解了一下网络编程&#xff0c;感觉理…

如何保证数据库和redis的数据一致性

1、简介 在客户端请求数据时&#xff0c;如果能在缓存中命中数据&#xff0c;那就查询缓存&#xff0c;不用在去查询数据库&#xff0c;从而减轻数据库的压力&#xff0c;提高服务器的性能。 2、问题如何保证两者的一致性 先更新数据库在删除缓存 难点&#xff1a;如何保证…