字符串匹配-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(一个全文…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
