【算法】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) 快速排序是一种分而治之的排序算法…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
