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-…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
