【算法】KMP算法
应用场景
- 有一个字符串 str1 = "BBA ABCA ABCDAB ABCDABD",和一个子串 str2 = "ABCDABD"
- 现在要判断 str1 是否含有 str2,如果含有,就返回第一次出现的位置,如果不含有,则返回 -1
我们很容易想到暴力匹配算法
暴力匹配算法
如果用暴力匹配的思路,并假设现在 str1 匹配到 i 位置,子串 str2 匹配到 j 位置,则有
- 如果当前字符匹配成功(即 str1[i] == str2[j]),则 i++,j++,继续匹配下一字符
- 如果匹配失败,令 i = i - j + 1,j = 0。相当于每次匹配失败时,i 回溯,j 被置为 0
- 用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量时间(不可行)
以下是代码实现暴力匹配
public class ViolenceMatch {public static void main(String[] args) {String str1 = "BBA ABCA ABCDAB ABCDABD";String str2 = "ABCDABD";System.out.printf("下标为%d", violenceMatch(str1, str2));}public static int violenceMatch(String str1, String str2) {char[] s1 = str1.toCharArray();char[] s2 = str2.toCharArray();int i = 0; //储存s1 的下标int j = 0; //储存s2 的下标while (i < s1.length && j < s2.length) {if (s1[i] == s2[j]) {i++;j++;} else {i = i - j + 1;j = 0;}}if (j == s2.length) {return i - j;}return -1;}
}
KMP算法
KMP算法介绍
KMP 算法利用之前判断过的信息,通过一个 next 数组,保存子串中前后最长公共子序列的长度,每次回溯时,通过 next 数组找到前面匹配过的位置,省去了大量计算时间
在学习KMP算法之前,我们先来聊一聊字符串的前缀与后缀

我们对子串 str2 建立一张《部分匹配表》

“部分匹配值”就是“前缀”和“后缀”的最长的共有元素的长度。以“ABCDABD”为例
“A”的前缀和后缀都为空集,共有元素的长度为0
“AB”的前缀为[A],后缀为[B],共有元素的长度为0
“ABC”的前缀为[A,AB],后缀为[BC,C],共有元素的长度为0
“ABCD”的前缀为[A,AB,ABC],后缀为[BCD,CD,D],共有元素的长度为0
“ABCDA”的前缀为[A,AB,ABC,ABCD],后缀为[BCDA,CDA,DA,A],共有元素为“A”,长度为 1
“ABCDAB”的前缀为[A,AB,ABC,ABCD,ABCDA],后缀为[BCDAB,CDAB,DAB,AB,B],共有元素为“AB”,长度为 1
“ABCDABD”的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB],后缀为[BCDABD,CDABD,DABD,ABD,BD,D],共有元素的长度为 0
已知空格与 D 不匹配时,前面六个字符“ABCDAB”是匹配的。查表可知,最后一个匹配字符 B 对应的“部分匹配值”为 2,因此按照下面的公式算出向后移动的位数:
移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 = 4,所以将搜索词向后移动 4 位
public class KMPAlgorithm {public static void main(String[] args) {String str1 = "BBA ABCA ABCDAB ABCDABD";String str2 = "ABCDABD";int[] next = kmpNext(str2);System.out.println("str1 = " + str1);System.out.println("str2 = " + str2);System.out.println("next = " + Arrays.toString(next));int index = kmpSearch(str1, str2, next);System.out.printf("索引为%d", index);}//写出 KMP搜索算法/**** @param str1* @param str2 子串* @param next 子串对应的部分匹配表* @return 返回第一个匹配的位置,如果是 -1 就没有匹配到*/public static int kmpSearch(String str1, String str2, int[] next) {//遍历for (int i = 0, j = 0; i < str1.length(); i++) {while (j > 0 && str1.charAt(i) != str2.charAt(j)) {j = next[j-1];}if (str1.charAt(i) == str2.charAt(j)) {j++;}if (j == str2.length()) { //找到了return i - j + 1;}}return -1;}//获取到一个子串的部分匹配值表public static int[] kmpNext(String dest) {//创建一个 next 数组保存部分匹配值int[] next = new int[dest.length()];next[0] = 0; //如果字符串的长度是 1,部分匹配值就是 0for (int i = 1, j = 0; i < dest.length(); i++) {//当 dest.charAt(i) != dest.charAt(j) 我们需要从 next[j-1]获取新的 j//直到 dest.charAt(i) == dest.charAt(j) 满足时,才退出//这是 KMP算法的核心点while (j > 0 && dest.charAt(i) != dest.charAt(j)) {j = next[j-1];}//当 dest.charAt(i) == dest.charAt(j) 满足时,部分匹配值就 +1if (dest.charAt(i) == dest.charAt(j)) {j++;}next[i] = j;}return next;}
}相关文章:
【算法】KMP算法
应用场景 有一个字符串 str1 "BBA ABCA ABCDAB ABCDABD",和一个子串 str2 "ABCDABD"现在要判断 str1 是否含有 str2,如果含有,就返回第一次出现的位置,如果不含有,则返回 -1 我们很容易想到暴力…...
nginx续1:
八、虚拟主机配置 基于域名的虚拟主机 [rootserver2 ~]# ps -au|grep nginx //查看进程 修改Nginx服务配置,添加相关虚拟主机配置如下 1. [rootproxy ~]# vim /usr/local/nginx/conf/nginx.conf 2. .. .. 3. server { 4. listen …...
循环队列和阻塞有什么关系?和生产者消费者模型又有什么关系?阻塞队列和异步日志又有什么关系
### 循环队列和阻塞队列 #### 循环队列 - **定义**: 一个固定大小的数组,通过两个指针(front 和 back)管理队列的头部和尾部元素。 - **特点**: - **循环性**: 当指针到达数组的末尾时,可以回绕到数组的开头,从而利…...
物理笔记-八年级上册
0.梦开始的地方 物理研究什么? 电学,力学,声学,光学,热学。 1.1.1长度的单位 国际基本单位制 单位转换 魔法记忆:千米-米-毫米-微米-纳米(进率都是1000) 单位换算计算方法 用科学…...
QT键盘和鼠标事件
这些事件都在QWidget 中的保护成员方法中 都是虚函数在头文件中声明了 需要类外重现实现 如果头文件中声明 类外无实现就会报错 void Widget::keyPressEvent(QKeyEvent *event) {switch (event->key()) {//获取按键case Qt::Key_W://按键wqDebug()<<"按下w"…...
文件Io编程基础
1. 标准I/O (stdio.h) stdio.h 是标准C库的头文件,包含了输入输出函数的声明。位置:/usr/include/stdio.h 2. 文件I/O操作步骤 打开文件: 使用 fopen 函数,返回 FILE* 指针。读/写操作: 使用 fread、fwrite、fgets、fputs、fprintf、fscan…...
本地项目提交到Gitee
在项目目录 右键 git bash here 可以在黑屏输入命令 也可以在项目里面 命令都是一样的 要排除哪些 git add . 添加所有文件 git commit -m "Initial commit" 提交到本地 git remote add origin https://gitee.com/xxxx/xxxx.git 添加远程仓库 …...
有了谷歌账号在登录游戏或者新APP、新设备时,要求在手机上点击通知和数字,怎么办?
有的朋友可能遇到过,自己注册或购买了谷歌账号以后,在自己的手机上可以正常登录,也完成了相关的设置,看起来一切都很完美,可以愉快地玩耍了。 但是,随后要登录一个游戏的时候(或者登录一个新的…...
rsyslog如何配置日志轮转
以下是在 Linux 系统中配置 rsyslog 日志轮转策略的一般步骤: 编辑 rsyslog 的配置文件,通常为 /etc/rsyslog.conf 或 /etc/rsyslog.d/*.conf 。 在配置文件中添加类似以下的日志轮转配置示例: $template myLogs,"/var/log/mylog-%Y%m%d…...
LLM推理入门实践:基于 Hugging Face Transformers 和 Qwen2模型 进行文本问答
文章目录 1. HuggingFace模型下载2. 模型推理:文本问答 1. HuggingFace模型下载 模型在 HuggingFace 下载,如果下载速度太慢,可以在 HuggingFace镜像网站 或 ModelScope 进行下载。 使用HuggingFace的下载命令(需要先注册Huggin…...
python:YOLO格式数据集图片和标注信息查看器
作者:CSDN _养乐多_ 本文将介绍如何实现一个可视化图片和标签信息的查看器,代码使用python实现。点击下一张和上一张可以切换图片。 文章目录 一、脚本界面二、完整代码 一、脚本界面 界面如下图所示, 二、完整代码 使用代码时࿰…...
AGI思考探究的意义、价值与乐趣 Ⅴ
搞清楚模型对知识或模式的学习与迁移对于泛化意味什么,或者说两者间的本质?相信大家对泛化性作为大语言模型LLM的突出能力已经非常了解了 - 这也是当前LLM体现出令人惊叹的通用与涌现能力的基础前提,这里不再过多赘述,但仍希望大家…...
c++: mangle命名规则
其实可用根据binutils/c++filt的源代码看。找到mangle的命名规则, 但是从网上找到了一个总结,但是github有时候上不去,摘录再次。 https://github.com/gchatelet/gcc_cpp_mangling_documentation https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling 举例: _ZN8…...
系统化学习 H264视频编码(05)码流数据及相关概念解读
说明:我们参考黄金圈学习法(什么是黄金圈法则?->模型 黄金圈法则,本文使用:why-what)来学习音H264视频编码。本系列文章侧重于理解视频编码的知识体系和实践方法,理论方面会更多地讲清楚 音视频中概念的…...
【VMware】如何演示使用U盘在VMware虚拟机上安装Windows11
一、前置准备 在开始使用U盘演示在VMware虚拟机上装Windows11前,我们需要做以下前置的准备: 已制作好的Windows引导盘;WMware软件 如何制作Windows引导盘? 推荐参考: 【建议收藏】2024年最新Windows系统重装教程&…...
HanLP和Jieba区别
HanLP和Jieba都是中文分词工具,但它们在多个方面存在区别。以下是对两者区别的详细分析: 一、开发背景与语言支持 HanLP:由大连理工大学自然语言处理与社会人文计算实验室开发,是一个开源的自然语言处理工具包。它主要使用Java语…...
荒原之梦考研:考研二战会很难吗?
考研二战是不是很难,其实很大程度上取决于我们自己,我们能否认清自己的优势,能否指定和执行合理的计划,有没有强大的心理支撑等,都是决定考研二战能否成功,或者能否比较轻松的成功的关键。 在本文中&#…...
【Git企业级开发实战指南①】Git安装、基本操作!
目录 一、Git是什么?1.1特点1.2功能1.3基本概念 二、Git安装2.1Ubuntu下安装2.2Centos下安装Git 三、Git基本操作3.1创建git本地仓库3.2配置Git3.3 工作区&暂存区&版本库3.4 实操案例3.4.1添加文件 3.5 修改文件3.6版本回退3.7查看历史操作日志3.7撤销修改3…...
Leetcode 3239. Minimum Number of Flips to Make Binary Grid Palindromic I
Leetcode 3239. Minimum Number of Flips to Make Binary Grid Palindromic I 1. 解题思路2. 代码实现 题目链接:3239. Minimum Number of Flips to Make Binary Grid Palindromic I 1. 解题思路 这一题思路上的话就是分别考察一下把所有行都变成回文所需要的fli…...
C++面试基础算法的简要介绍
C是一种广泛使用的编程语言,尤其在算法和数据结构的实现中占据重要地位。以下是对C基础算法的一些介绍,涵盖了排序、查找、搜索算法以及基本的遍历算法等方面。 排序算法 快速排序(Quick Sort) 快速排序是一种分而治之的排序算法…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
负载均衡器》》LVS、Nginx、HAproxy 区别
虚拟主机 先4,后7...
