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

字符串匹配-KMP算法

KMP算法,字符串匹配算法,给定一个主串S,和一个字串T,返回字串T与之S匹配的数组下标。

在学KMP算法之前,对于两个字符串,主串S,和字串T,我们根据暴力匹配,定义两个指针,i指向主串S的起始,j指向字串T的起始,依次比较,如果主串i位置的值等于子串j位置的值,i++,j++。直到i位置的值和j位置的值不相同,i回溯到起始位置+1,同时字串T的起始位置后移到i所在位置。直到匹配成功,或者子串T后移长度+T本身长度>S主串的长度。这个暴力求解的复杂度,因为有i的回溯,需要2层循环i,j的移动,因此时间复杂度为T(n*m),n是S的长度,m是T的长度。

根据暴力匹配的思想,我们接下来分析一下KMP算法。同样两个字符串按位比较,而KMP算法的核心在于,当主串的i位置的值和子串的j位置的值不同时,主串S,i前面的字符串与字串T,j前面的字符串已经匹配相等,因为两者相等,所以只需要拿出子串T前面的字符串,根据T前面的字符串来计算一个next[j]数组,将j回溯即可。问题便转换为求子串的next[j]数组。那么next[j]数组的求法为,i前面的字符串,分别取前缀和取后缀,如果前缀的长度=后缀的长度,则j的值=字符串缀长+1存入next数组。否则,j回溯给next[j]。直到j=字串长度,则next数组计算完成。后续根据i不回溯,j从next数组里取值,便可将字串T和主串S进行匹配,直到字串T移出到主串S的长度,匹配成功返回i下标,匹配失败返回0。因为KMP算法简化了问题的求解,将难点转换为求next数组,并且i不回溯,可以做到边移动边匹配。因此,时间复杂度为T(n+m)

下面是JAVA实现代码

  public static void main(String[] args) {String S  = "abababcabcabc";String T  = "bcabc";int pos = KMP(S,T);System.out.println(pos);}private static int KMP(String s, String t) {int i = 0;//i指向Sint j = 0;//j指向Twhile (i<s.length()&&j<t.length()){if(j==-1||s.charAt(i)==t.charAt(j)){//为什么j==-1,i和j也需要后移,当j==-1,说明字串和主串的起始点在0,i++;//i后移j++;//j后移}else{j = getNext(t)[j]; //j根据t求一个next数组,next数组的作用就是j根据内部的值回溯。}}if(j == t.length()){  //j已经等于t的长度了,说明匹配结束了。return i-t.length();  //字串起始点就是i-j或者i-t.length()}else{return -1;//匹配失败了。}}private static int[] getNext(String t) {int i = 0;//next数组下标,初始值0int j = -1;//j指向字符串t,初始值-1int [] next = new int[t.length()];//构造next数组,长度为t的长度。next[0] = -1;//next数组从1开始存值,即0号位置存默认值-1;while (i<t.length()-1){if(j==-1||t.charAt(i)==t.charAt(j)){//j==-1表示从头开始遍历t,或者t的前缀==t的后缀,都要将j+1存入next数组i++;j++;next[i] =  j;  //如果后缀==前缀,将j+1,即j++的值存入next数组。}else {j = next[j]; //如果后缀!=前缀,j回溯到next[j]位置}}return next;}

输出结果:

5

完全正确。

相关文章:

字符串匹配-KMP算法

KMP算法&#xff0c;字符串匹配算法&#xff0c;给定一个主串S&#xff0c;和一个字串T,返回字串T与之S匹配的数组下标。 在学KMP算法之前&#xff0c;对于两个字符串&#xff0c;主串S&#xff0c;和字串T&#xff0c;我们根据暴力匹配&#xff0c;定义两个指针&#xff0c;i指…...

Java面向对象之UML类图

UML类图 表示 public 类型&#xff0c; - 表示 private 类型&#xff0c;#表示protected类型方法的写法&#xff1a;方法的类型(、-) 方法名(参数名&#xff1a; 参数类型)&#xff1a;返回值类型...

【机器学习】西瓜书学习心得及课后习题参考答案—第4章决策树

这一章学起来较为简单&#xff0c;也比较好理解。 4.1基本流程——介绍了决策树的一个基本的流程。叶结点对应于决策结果&#xff0c;其他每个结点则对应于一个属性测试&#xff1b;每个结点包含的样本集合根据属性测试的结果被划分到子结点中&#xff1b;根结点包含样本全集&a…...

2023.8.2

2022河南萌新联赛第&#xff08;三&#xff09;场&#xff1a;河南大学\神奇数字.cpp //题意&#xff1a;给定三个正整数a b c,求x满足满足abc同余x的个数。 //这个考虑同余的性质&#xff0c;就是两个数的差去取模为0的数肯定是这两个数的同余数,。因此我们计算三个数两两之…...

windows运行窗口常用快捷键命令

winr打开运行窗口,然后输入快捷命令:&#xff08;当然utools和win11搜索也挺好用的&#xff09; cmd : 命令行窗口&#xff08;命令提示符窗口、cmd窗口&#xff09;regedit : 注册表mspaint : 画图工具services.msc : 本地服务设置(比如查看mysql服务是否启动成功)devmgmt.ms…...

HDFS的QJM方案

Quorum Journal Manager仲裁日志管理器 介绍主备切换&#xff0c;脑裂问题解决---ZKFailoverController&#xff08;zkfc&#xff09;主备切换&#xff0c;脑裂问题解决-- Fencing&#xff08;隔离&#xff09;机制主备数据状态同步问题解决 HA集群搭建集群基础环境准备HA集群规…...

安装win版本的neo4j(2023最新版本)

安装win版本的neo4j 写在最前面安装 win版本的neo4j1. 安装JDK2.下载配置环境变量&#xff08;也可选择直接点击快捷方式&#xff0c;就可以不用配环境了&#xff09;3. 启动neo4j 测试代码遇到的问题及解决&#xff08;每次环境都太离谱了&#xff0c;各种问题&#xff09;连接…...

ChatGPT结合知识图谱构建医疗问答应用 (二) - 构建问答流程

一、ChatGPT结合知识图谱 上篇文章对医疗数据集进行了整理&#xff0c;并写入了知识图谱中&#xff0c;本篇文章将结合 ChatGPT 构建基于知识图谱的问答应用。 下面是上篇文章的地址&#xff1a; ChatGPT结合知识图谱构建医疗问答应用 (一) - 构建知识图谱 这里实现问答的流程…...

聊天系统登录后端实现

定义返回的数据格式 # Restful API from flask import jsonifyclass HttpCode(object):# 响应正常ok 200# 没有登陆错误unloginerror 401# 没有权限错误permissionerror 403# 客户端参数错误paramserror 400# 服务器错误servererror 500def _restful_result(code, messa…...

Ajax笔记_01(知识点、包含代码和详细解析)

Ajax_01笔记 前置知识点 在JavaScript中 问题1&#xff1a;将数组转为字符串&#xff0c;以及字符串转为数组的方式。 问题2、将对象转为字符串&#xff0c;以及字符串转为对象的方法。 方法&#xff1a; 问题1&#xff1a; 将数组转为字符串可以使用 join() 方法。例如&…...

Eureka 学习笔记2:EurekaClient

版本 awsVersion ‘1.11.277’ EurekaClient 接口实现了 LookupService 接口&#xff0c;拥有唯一的实现类 DiscoveryClient 类。 LookupService 接口提供以下功能&#xff1a; 获取注册表根据应用名称获取应用根据实例 id 获取实例信息 public interface LookupService<…...

Spring引入并启用log4j日志框架-----Spring框架

<?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 http://ma…...

Redis实现延时队列

缓存队列延时向接口报工&#xff0c;并支持多实例部署。 引入依赖 <dependency><groupId>org.redisson</groupId><artifactId>redisson-spring-data</artifactId><version>3.17.4</version> </dependency> 注入RedisClient …...

无限遍历,Python实现在多维嵌套字典、列表、元组的JSON中获取数据

目录 背景 思路 新建两个函数A和B&#xff0c;函数 A处理字典数据&#xff0c;被调用后&#xff0c;判断传递的参数&#xff0c;如果参数为字典&#xff0c;则调用自身&#xff1b; 如果是列表或者元组&#xff0c;则调用列表处理函数B&#xff1b; 函数 B处理列表&#x…...

信息学奥赛一本通——1180:分数线划定

文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】【提示】 AC代码 题目 【题目描述】 世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才&#xff0c;A市对所有报名的选手进行了笔试&#xff0c;笔试分数达到面试分数线的选手方可进入…...

SpringApplication对象的构建及spring.factories的加载时机

构建SpringApplication对象源码: 1、调用启动类的main()方法,该方法中调用SpringApplication的run方法。 SpringBootApplication public class SpringbootdemoApplication {public static void main(String[] args) {SpringApplication.run(SpringbootdemoApplication.class, …...

基于传统检测算法hog+svm实现图像多分类

直接上效果图&#xff1a; 代码仓库和视频演示b站视频005期&#xff1a; 到此一游7758258的个人空间-到此一游7758258个人主页-哔哩哔哩视频 代码展示&#xff1a; 数据集在datasets文件夹下 运行01train.py即可训练 训练结束后会保存模型在本地 运行02pyqt.py会有一个可视化…...

slice() 方法,使用 concat() 方法, [...originalArray],find(filter),移出类名 removeAttr()

在JavaScript中&#xff0c;在 JavaScript 中&#xff0c;clone 不是一个原生的数组方法。但是你可以使用其他方法来实现克隆数组的功能。 以下是几种常见的克隆数组的方法&#xff1a; 使用 slice() 方法&#xff1a; const originalArray [1, 2, 3]; const clonedArray …...

Zabbix报警机制、配置钉钉机器人、自动发现、主动监控概述、配置主动监控、zabbix拓扑图、nginx监控实例

day02 day02配置告警用户数超过50&#xff0c;发送告警邮件实施验证告警配置配置钉钉机器人告警创建钉钉机器人编写脚本并测试添加报警媒介类型为用户添加报警媒介创建触发器创建动作验证自动发现配置自动发现主动监控配置web2使用主动监控修改配置文件&#xff0c;只使用主动…...

ELK日志分析系统概述及部署

ELK 平台是一套完整的日志集中处理解决方案&#xff0c;将 ElasticSearch、Logstash 和 Kibana 三个开源工具配合使用&#xff0c;完成更强大的用户对日志的查询、排序、统计需求。 一、ELK概述 1、组件说明 ①ElasticSearch ElasticSearch是基于Lucene&#xff08;一个全文…...

后进先出(LIFO)详解

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

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...