字符串匹配-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算法,字符串匹配算法,给定一个主串S,和一个字串T,返回字串T与之S匹配的数组下标。 在学KMP算法之前,对于两个字符串,主串S,和字串T,我们根据暴力匹配,定义两个指针,i指…...
Java面向对象之UML类图
UML类图 表示 public 类型, - 表示 private 类型,#表示protected类型方法的写法:方法的类型(、-) 方法名(参数名: 参数类型):返回值类型...
【机器学习】西瓜书学习心得及课后习题参考答案—第4章决策树
这一章学起来较为简单,也比较好理解。 4.1基本流程——介绍了决策树的一个基本的流程。叶结点对应于决策结果,其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集&a…...
2023.8.2
2022河南萌新联赛第(三)场:河南大学\神奇数字.cpp //题意:给定三个正整数a b c,求x满足满足abc同余x的个数。 //这个考虑同余的性质,就是两个数的差去取模为0的数肯定是这两个数的同余数,。因此我们计算三个数两两之…...
windows运行窗口常用快捷键命令
winr打开运行窗口,然后输入快捷命令:(当然utools和win11搜索也挺好用的) cmd : 命令行窗口(命令提示符窗口、cmd窗口)regedit : 注册表mspaint : 画图工具services.msc : 本地服务设置(比如查看mysql服务是否启动成功)devmgmt.ms…...
HDFS的QJM方案
Quorum Journal Manager仲裁日志管理器 介绍主备切换,脑裂问题解决---ZKFailoverController(zkfc)主备切换,脑裂问题解决-- Fencing(隔离)机制主备数据状态同步问题解决 HA集群搭建集群基础环境准备HA集群规…...
安装win版本的neo4j(2023最新版本)
安装win版本的neo4j 写在最前面安装 win版本的neo4j1. 安装JDK2.下载配置环境变量(也可选择直接点击快捷方式,就可以不用配环境了)3. 启动neo4j 测试代码遇到的问题及解决(每次环境都太离谱了,各种问题)连接…...
ChatGPT结合知识图谱构建医疗问答应用 (二) - 构建问答流程
一、ChatGPT结合知识图谱 上篇文章对医疗数据集进行了整理,并写入了知识图谱中,本篇文章将结合 ChatGPT 构建基于知识图谱的问答应用。 下面是上篇文章的地址: 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:将数组转为字符串,以及字符串转为数组的方式。 问题2、将对象转为字符串,以及字符串转为对象的方法。 方法: 问题1: 将数组转为字符串可以使用 join() 方法。例如&…...
Eureka 学习笔记2:EurekaClient
版本 awsVersion ‘1.11.277’ EurekaClient 接口实现了 LookupService 接口,拥有唯一的实现类 DiscoveryClient 类。 LookupService 接口提供以下功能: 获取注册表根据应用名称获取应用根据实例 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实现延时队列
缓存队列延时向接口报工,并支持多实例部署。 引入依赖 <dependency><groupId>org.redisson</groupId><artifactId>redisson-spring-data</artifactId><version>3.17.4</version> </dependency> 注入RedisClient …...
无限遍历,Python实现在多维嵌套字典、列表、元组的JSON中获取数据
目录 背景 思路 新建两个函数A和B,函数 A处理字典数据,被调用后,判断传递的参数,如果参数为字典,则调用自身; 如果是列表或者元组,则调用列表处理函数B; 函数 B处理列表&#x…...
信息学奥赛一本通——1180:分数线划定
文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】【提示】 AC代码 题目 【题目描述】 世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入…...
SpringApplication对象的构建及spring.factories的加载时机
构建SpringApplication对象源码: 1、调用启动类的main()方法,该方法中调用SpringApplication的run方法。 SpringBootApplication public class SpringbootdemoApplication {public static void main(String[] args) {SpringApplication.run(SpringbootdemoApplication.class, …...
基于传统检测算法hog+svm实现图像多分类
直接上效果图: 代码仓库和视频演示b站视频005期: 到此一游7758258的个人空间-到此一游7758258个人主页-哔哩哔哩视频 代码展示: 数据集在datasets文件夹下 运行01train.py即可训练 训练结束后会保存模型在本地 运行02pyqt.py会有一个可视化…...
slice() 方法,使用 concat() 方法, [...originalArray],find(filter),移出类名 removeAttr()
在JavaScript中,在 JavaScript 中,clone 不是一个原生的数组方法。但是你可以使用其他方法来实现克隆数组的功能。 以下是几种常见的克隆数组的方法: 使用 slice() 方法: const originalArray [1, 2, 3]; const clonedArray …...
Zabbix报警机制、配置钉钉机器人、自动发现、主动监控概述、配置主动监控、zabbix拓扑图、nginx监控实例
day02 day02配置告警用户数超过50,发送告警邮件实施验证告警配置配置钉钉机器人告警创建钉钉机器人编写脚本并测试添加报警媒介类型为用户添加报警媒介创建触发器创建动作验证自动发现配置自动发现主动监控配置web2使用主动监控修改配置文件,只使用主动…...
ELK日志分析系统概述及部署
ELK 平台是一套完整的日志集中处理解决方案,将 ElasticSearch、Logstash 和 Kibana 三个开源工具配合使用,完成更强大的用户对日志的查询、排序、统计需求。 一、ELK概述 1、组件说明 ①ElasticSearch ElasticSearch是基于Lucene(一个全文…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
Java多线程实现之Runnable接口深度解析
Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...
Qt Quick Controls模块功能及架构
Qt Quick Controls是Qt Quick的一个附加模块,提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中,这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构,与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...
Ray框架:分布式AI训练与调参实践
Ray框架:分布式AI训练与调参实践 系统化学习人工智能网站(收藏):https://www.captainbed.cn/flu 文章目录 Ray框架:分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...
