13-数据结构-串以及KMP算法,next数组
串
目录
串
一、串:
二、串的存储结构:
三、模式匹配
1.简单模式匹配(BF算法)
2.KMP算法
2.1-next(j)数组手工求解
2.2-nextval(j)数组手工求解
一、串:
内容受限的线性表,也就是相当于C语言里的字符串,只不过这里字符串从1开始存取。
此外串里包含子串,每个字串的第一个元素位置为该字串在串中的位置,每个串里面必有一个空串,此外,数串的时候,遇到重复的,只保留一个。
kmp算法就是根据相应的字串(模式串)取查找相应位置的操作,
串的长度,实际上为字符串长度。而数组长度为串的长度+1+1,从数组1开始存,因此+1,最后字符串结尾\'0’也要存。
二、串的存储结构:
静态顺序存储,就是定义一个固定长度的字符数组,再多一个记录个数的变量。
堆分配存储,就是动态数组,malloc一个空间,空间大小为sizeof(char)*(max+2);
块链存储:就是单链表的基础上,多了好多存储数据的变量,因此一块结点,好几个变量存进去。
串的基本操作:
SteCompare(S,T),就是C语言里的字符串比较,实际操作为:S-T,若结果小于0,则S<T,若结果大于0,则S大于T,S、T为字符串。
Concat(*T,S1,S2),给S2连接到S1后面,组成新的串,赋值给T串,返回。
SubStrin(*Sub,S,pos,len),返回串S中,第pos位置起,长度为len的字串
Index(S,T,Pos),模式匹配,S中第pos位置起,与字串T相等的串。并返回该串再S中出现的第一次的位置。
三、模式匹配
1.简单模式匹配(BF算法)
模式匹配,就是有一个字串(模式串),取对应的主串里,找与它一样的,并返回它在主串中的位置,
简单模式匹配,就是主串在上,模式串在下,动主串坐标,取挨个对比。
设i为记录主串的下标,j为模式串的下标,k则是记录每次回溯,比对的次数。
当i和j中的值都相等时,都往后移动,当不匹配时,则进行下标的更新,主串中的i,更新为i=k+1,即主串的i从左至右,挨个比对,第一个开始,比对失败,则第二个开始,重新比对。模式串则时更新为j=1,因为,每次重新比对,所以,模式串每次更新都是从1开始。
简单模式匹配算法为(m*n),主串长为m,模式串为n,因为最坏的情况,每次主串都要重新比对,所以为m,而每次比对,模式串都需要从头到尾重新遍历,所以m*n
2.KMP算法
kmp时间复杂度为O(m+n),KMP算法主要是模式串下标动,更新,主串中的i会一直增加,不会出现回溯的现象。
2.1-next(j)数组手工求解
在简单模式匹配的基础上,优化。即next(j)数组,是记录,每次模式串比对失败时,模式串下标的更新的起始值。如果模式串下标j==0,则i++,j++,即简单匹配操作,否则,主串不需要动,模式串下标更新动即可。
而next(j)数组,怎么求嘞,next数组,就是给模式串每一个位置处,匹配失败,时,跟新的下标值都记录下来。所以手工怎么计算呢?
分两部分,当第一个位置处时,j直接更新为0,因为第一个位置前,无数据,没法拿来进行找重复部分的长度。第二个位置时,则找第一个位置,然后错一位,进行比对,比对时,下面的那一串向右移动,直到比对完重复部分,之后重复部分长度+1,便是模式串下标所更新的值。
具体看讲义,不好画图
2.2-nextval(j)数组手工求解
nextval数组,则是在,next的基础上,再优化。即,当next数组求的坐标的内容,与原来不匹配的坐标内容一致时,可直接,给nextval中,当前不匹配情况,与所求最新的,坐标相同即可。
具体看讲义,不好画图。
相关文章:
13-数据结构-串以及KMP算法,next数组
串 目录 串 一、串: 二、串的存储结构: 三、模式匹配 1.简单模式匹配(BF算法) 2.KMP算法 2.1-next(j)数组手工求解 2.2-nextval(j)数组手工求解 一、串: 内容受…...
Stable Diffusion - 俯视 (from below) 拍摄的人物图像 LoRA 与配置
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/132192139 图像来自 哥特风格 LoRA 俯视 LoRA,提升视觉冲击力,核心配置 <lora:view_from_below:0.6>,(from below,…...
Redis——String类型详解
概述 Redis中的字符串直接按照二进制的数据存储,不会有任何的编码转换,因此存放什么样,取出来的时候就什么样。而MySQL默认的字符集是拉丁文,如果插入中文就会失败 Redis中的字符串类型不仅可以存放文本数据,还可以存…...
Android:换肤框架Android-Skin-Support
gihub地址:https://github.com/ximsfei/Android-skin-support 样例: 默认: 更换后: 一、引入依赖: // -- 换肤依赖implementation skin.support:skin-support:4.0.5// skin-supportimplementation skin.support:ski…...
软件测试面试心得:四种公司、四种问题…
以下是我个人总结的一些经验: 传统开发模式:V模式,瀑布模式。传统开发模式往往循规蹈矩,从需求,概要设计,详细设计,开发,单元测试,集成测试,系统测…...
【探索SpringCloud】服务发现-Nacos使用
前言 在聊服务注册中心时,便提到了Nacos。这次便来认识一下。当然,这自然没有官方介绍那般详尽,权当是学习了解Nacos原理的一个过程吧。 Nacos简介 Nacos,全名:dynamic Naming And Configuration Service. 而这个名…...
soap通信2
首先,定义一个XSD(XML Schema Definition)来描述你的数据结构。在你的Maven项目的src/main/resources目录下,创建一个名为schemas的文件夹,并在其中创建一个名为scriptService.xsd的文件,内容如下ÿ…...
【MySQL】MySQL不走索引的情况分析
未建立索引 当数据表没有设计相关索引时,查询会扫描全表。 create table test_temp (test_id int auto_incrementprimary key,field_1 varchar(20) null,field_2 varchar(20) null,field_3 bigint null,create_date date null );expl…...
JVM垃圾回收篇-垃圾回收算法
JVM垃圾回收篇-垃圾回收算法 标记清除(Mark Sweep) 概念 collector指的就是垃圾收集器。 mutator是指除了垃圾收集器之外的部分,比如说我们的应用程序本身。 mutator的职责一般是NEW(分配内存)、READ(从内存中读取内容)、WRITE(将内容写入内…...
android APP内存优化
Android为每个应用分配多少内存 Android出厂后,java虚拟机对单个应用的最大内存分配就确定下来了,超出这个值就会OOM。这个属性值是定义在/system/build.prop文件中. 例如,如下参数 dalvik.vm.heapstartsize8m #起始分配内存 dalvik.vm.…...
mysql_docker主从复制_实战_binlog混合模式_天座著
步骤1:拉取镜像 docker pull mariadb:latest 步骤2.1:创建两个文件夹用于放置挂载mysql的my.cnf /tianzuomysqlconf/master /tianzuomysqlconf/slave mkdir /tianzuomysqlconf cd /tianzuomysqlconf mkdir master mkdir slave 步骤2.2:创…...
鸿蒙开发学习笔记1——真机运行hello world
问题背景 学习任何语言和框架的第一步,永远都是跑通熟悉的“hello world”,本文将介绍鸿蒙开发如何跑通“hello world”。 问题分析 一、构建第一个ArkTS应用(fa模型) 说明:请使用DevEco Studio V3.0.0.601 Beta1及…...
Java数组,简简单单信手沾来~
——数组,一组相同数据类型的数据 一.一维数组 1.数组的基本概念 1)数组用于存储多个同一数据类型的数据 2)数组是数据类型【引用类型】 3)数组的形式:数据类型 [] 4)数组的下标从0开始 5)数…...
认识SourceTree
一. SourceTree是什么 SourceTree是一款免费的Git和Mercurial版本控制系统,它可以帮助开发人员在一个友好的UI界面中管理代码,方便地进行版本控制和代码同步。支持创建、克隆、提交、push、pull 和合并等操作。 二. SourceTree的安装破解 1. 如果你还…...
python之列表推导式
列表推导式是一种简洁的方式来创建列表。它允许您通过在单个表达式中定义循环和条件逻辑,以一种更紧凑的方式生成新的列表。使用列表推导式可以使代码更简洁,易于阅读,并且通常比传统的迭代方法更快。 列表推导式的一般语法形式为:…...
selenium自动化测试之搭建测试环境
自动化测试环境: Python3.7Selenium3.141谷歌浏览器76.0/火狐浏览器 1、安装Python并配置环境变量。 下载并安装:配置环境变量:C:\Python37;C:\Python37\Scripts; 2、安装Pycharm开发工具。 下载地址: 注意下载:Co…...
模拟实现消息队列(以 RabbitMQ 为蓝本)
目录 1. 需求分析1.1 介绍一些核心概念核心概念1核心概念2 1.2 消息队列服务器(Broker Server)要提供的核心 API1.3 交换机类型1.3.1 类型介绍1.3.2 转发规则: 1.4 持久化1.5 关于网络通信1.5.1 客户端与服务器提供的对应方法1.5.2 客户端额外…...
WordPress更换域名后-后台无法进入,网站模版错乱,css失效,网页中图片不显示。完整解决方案(含宝塔设置)
我在实际解决问题时用到了 【简单暴力解决方案】的《方法一:修改wp-config.php》 和 【简单暴力-且特别粗暴-的解决方案】 更换域名时经常遇到的几个问题: 1、更换域名后,后台无法进入 2、更换域名后,网站模版错乱,css失效 3、更换域名后,网页中图片不显示 这是为什…...
无法正确识别车牌(Python、OpenCv、Tesseract)
我正在尝试识别车牌,但出现了错误,例如错误/未读取字符 以下是每个步骤的可视化: 从颜色阈值变形关闭获得遮罩 以绿色突出显示的车牌轮廓过滤器 将板轮廓粘贴到空白遮罩上 Tesseract OCR的预期结果 BP 1309 GD 但我得到的结果是 BP 1309…...
VSCODE[配置ssh免密远程登录]
配置ssh免密远程登录 本文摘录于:https://blog.csdn.net/qq_44571245/article/details/123031276只是做学习备份之用,绝无抄袭之意,有疑惑请联系本人! 这里要注意如下几个地方: 1.要进入.ssh目录创建文件: 2.是拷贝带"ssh-…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
