【算法】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) 快速排序是一种分而治之的排序算法…...
Ryzen SDT调试工具:解锁AMD处理器隐藏性能的终极指南
Ryzen SDT调试工具:解锁AMD处理器隐藏性能的终极指南 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: https://git…...
Nunchaku-flux-1-dev模型服务监控:使用Node.js搭建性能仪表盘
Nunchaku-flux-1-dev模型服务监控:使用Node.js搭建性能仪表盘 你是不是也遇到过这种情况?自己部署的AI模型服务,用着用着突然就变慢了,或者干脆没响应了,用户反馈过来才知道出了问题。等到发现的时候,可能…...
成为技术专家的捷径?不,只有长期主义的坚持
在软件测试领域,我们常常被一种“速成”的幻象所包围。铺天盖地的培训广告承诺“三个月精通自动化测试”、“六周成为性能测试专家”,各种“一招鲜”的测试工具和“万能”的测试框架被包装成通往成功的捷径。对于身处其中、渴望突破职业瓶颈的测试工程师…...
Cocos Creator 屏幕适配实战:从设计分辨率到完美适配的完整指南
1. 理解屏幕适配的核心概念 第一次用Cocos Creator做横屏游戏时,我盯着iPad和手机上完全变形的UI界面愣了半天。这才明白为什么老司机们总说:"屏幕适配不做,上线火葬场"。屏幕适配的本质是解决设计分辨率(美术产出资源时…...
解决Python ssl模块与系统OpenSSL版本不一致的编译指南
1. 为什么Python的ssl模块会与系统OpenSSL版本不一致? 很多开发者都遇到过这样的困惑:明明系统已经升级了OpenSSL,为什么Python的ssl模块还在使用旧版本?这个问题其实源于Python的编译机制。Python在编译安装时,会将当…...
ARP 协议超详细讲解
前言网络设备有数据要发送给另一台网络设备时,必须要知道对方的网络层地址(即IP地址)。IP地址由网络层来提供,但是仅有IP地址是不够的,IP数据报文必须封装成帧才能通过数据链路进行发送。数据帧必须要包含目的MAC地址&…...
别再看水刊了!智能故障诊断领域投稿,这20+个SCI期刊才是你的目标(附避坑指南)
智能故障诊断领域投稿指南:20高价值SCI期刊与避坑策略 对于从事智能故障诊断研究的学者而言,选择合适的SCI期刊投稿是研究成果获得认可的关键一步。本文将系统梳理该领域的优质期刊资源,帮助您避开常见陷阱,提高投稿成功率。 1. 智…...
前端测试的学习阶段,由基础到进阶的过程认识.....
前言:突然想起刚入行的学习感悟,一个知识点不懂的背后,是整个知识体系的欠缺, 那会从后端转入前端(非科班)有时候一个报错不知道从何找起,一、单元测试 【已经案例和知识相结合,可看…...
从MATLAB/Python代码实现反推Newmark-β法:理解线性加速度假设如何变成迭代算法
从代码实现反推Newmark-β法:线性加速度假设的工程实践指南 在结构动力学分析中,地震响应、风荷载等时程分析问题常需要求解二阶微分方程。Newmark-β法作为经典数值解法,通过线性加速度假设将连续问题离散化。但教科书往往止步于公式推导&am…...
WarcraftHelper:魔兽争霸III现代化增强工具全面指南
WarcraftHelper:魔兽争霸III现代化增强工具全面指南 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 如何让经典游戏适配现代硬件环境&…...
