当前位置: 首页 > 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;一个全文…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

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

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

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...