Java【KMP算法】大白话式详细图文解析(附代码)
前言
本篇为大家介绍KMP算法,力求用最白话,最通俗的文字让你学会KMP算法✌️!!!
提示:是正在努力进步的小菜鸟一只,如有大佬发现文章欠佳之处欢迎批评指点~ 废话不多说,直接上干货!
文章目录
一、KMP算法是什么
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth👨🏻🦳,J.H.Morris👨🏻🦳和V.R.Pratt👨🏻🦳提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
KMP算法的核心是利用匹配失败❌后的信息,尽量减少模式串与主串的匹配次数🔢以达到快速匹配🔜的目的。具体实现的核心就是通过一个 next()函数实现,函数本身包含了模式串的局部匹配信息。
以上是百度百科的概念,相信没学过 KMP 算法的小伙伴第一次看到都一脸懵逼😿,没关系,本篇将通俗的,白话的,详细的,让你学会 KMP !
🚗🚗🚗
先看概念解释的第一句: “KMP算法是一种改进的字符串匹配算法”
那么我们先了解一下最最最原始的 BF(暴力匹配)算法的过程:
👉什么是字符串匹配?
比如一个字符串:“abcababcabc” 作为主串❗️
要在这个主串中找到 “abcabc” ,则"abcabc" 被称作子串❗️
利用 i 和 j 下标分别访问这两个字符串的字符
依次匹配,直到在主串中找到完整的子串
👉BF算法过程简述
主串和当子串中的 “abcab” 匹配完之后,发现下一个字符 “c” 和主串的下一个字符 “a” 不匹配❎
那么 BF 算法就直接将 j 移动到子串的起点, i 移动到主串的下一个字符处(如图)
用子串的第一个字符 “a” 去比较主串的下一个字符 “c”
👇👇👇
虽然BF算法也可以实现字符串匹配,但还有需要改进的地方
假设匹配子串时,多次中途匹配失败,每一次子串都需要从头再来,这就是缺陷❎
举一个通俗的栗子:你在跨栏比赛🏃,中途跨栏失败了一次
BF算法就惩罚你,让你从起点重新跑
而KMP算法会为你安排一个合适的惩罚,可能是让你后退2️⃣米,可能让你后退2️⃣0️⃣米,也有可能让你从头跑
KMP就一定程度上节省了你的体力
而在计算机中,节省了时间,提高了效率
下面我们看看KMP算法的思想
二、解析KMP算法
1.KMP算法的思想
我们还拿刚刚的字符串 “abcababcabc” 举例
👇👇👇
👉再换句话强调一下这样移动的目的:
匹配失败后,在主串 已经匹配成功 的一部分中找到 和子串最大程度已经匹配 的一部分
这一部分就是此时主串的绿色方块🟩和子串的蓝色方块🟦
⚠️ 这是理解KMP算法的第一步!万事开头难,如果你理解了这个思想,就离胜利不远了!!
蓝色方块 / 绿色方块的长度专业术语是 “前缀 / 后缀最长相等长度” , j 移动的过程专业术语是 “回溯”
本篇不需要这些专业名词,跟着作者的思路你也能理解!
然后问题紧接着来了,程序是如何知道 j 移动到哪里的❓
👉首先,我们获取主串和子串中的字符是利用 charAt() 这个方法:字符串变量名 + 点号 + charAt(下标)
String str = "ababcabcdabcdefg";
char ch1 = str.charAt(0);
char ch2 = str.charAt(1);
System.out.println(ch1);// 结果为 a
System.out.println(ch2);// 结果为 b
👉然后,子串对应着有一个 next数组,其中存放数字
注意!!,next数组是和子串绑定的
上图中,子串里,绿色方块🟩后的字符 “c” 对应的next数组中就存了一个数字 “2”,那么 j 移动的时候就移动到字符串中下标为 “2” 的位置去
这就是 next数组 的作用,它相当于一个告示牌🔙,告诉 j 匹配失败后该去哪里
还记得我刚才举的跨栏的栗子嘛
如果我在第 5️⃣个障碍栏处摔倒,这个障碍栏上写了个数字 2️⃣ ,那我就从第2️⃣个障碍栏开始重跑,而不是从0️⃣开始
如果我就是倒霉🥚,摔倒处的障碍栏上写个0️⃣,那我就得从0️⃣开始重跑了咯
next数组 就是KMP算法的核心 !!!
👉那么next数组中存放的数字如何求得呢?往下看
2.next数组(核心)
刚才说到:
子串里,绿色方块🟩后的字符 “c” 对应的next数组中就存了一个数字 “2” ,为什么是 “2” 呢?为啥不是 “3” ?不是 “100” ?
👇👇👇
问题又来了,蓝色方块🟦和绿色方块🟩是我肉眼👀找出来的,那么程序是如何找到蓝色方块🟦呢?换句话说,程序如何计算 j 移动到的下标位置是几呢❓
2.1, next数组 的计算规则
接下来就要解析一下 next数组 的计算规则
👇👇👇
我们用 肉眼👀 推导出来了 next数组
next[0] 为什么是 -1 ,next[1] 为什么是 0 ,咱们待会再说
我知道你可能很急,但你先别急
代码里应该是先定义一个 next数组 (和子串长度相等) ,然后写一个 getNext 方法得到 next数组 中的值,那么 getNext 方法的代码如何写呢,马上来啦!
2.2, 新的变量 K
👇👇👇
注意:k 的值就是我们所说的,子串匹配失败后 j 移动(回退)🔙到的位置 ,继续往下看
2.3, 期望情况 : charAt( j-1 ) == charAt( k )✅
👇👇👇
2.4, 非期望情况 : charAt( j-1 ) != charAt( k )❎
👇👇👇
通过这两种情况的情况的对比分析可知
1,第1️⃣种情况才是理想的,我们希望发生的
2,如果发生第2️⃣种情况,我们就想办法改变现状,变成第1️⃣种情况,就是让 k 一直回退🔙,每次回退之后就判断是否满足第1️⃣种情况,直到满足第1️⃣种情况的条件为止
至此我们已经用 肉眼👀 和 代码⌨️ 的方式分析了 next数组 的计算过程, 现在趁热打铁,上代码解析📝!
2.4, 分析 next[0] 和 next[1] 的取值
❗️ 各位的疑惑在这里解开啦 ❗️
前面我们遗留了 next[0] 为什么是 -1 和 next[1] 为什么是 0 这两个问题
小伙伴们仔细看!
👇👇👇
三、KMP算法完整代码
public static void getNext(int[] next, String sub) {
next[0] = -1;
if(sub.length() == 1) {
// 当子串只有一个数据的时候,next数组的长度为1
return;
}
// 前提条件是数组长度大于1
next[1] = 0;
int k = 0;
int j = 2;
while(j < sub.length()) {
if(k == -1 || sub.charAt(j - 1) == sub.charAt(k)) {
next[j] = k + 1;
j++;
k++;
}else {
k = next[k];
}
}
}
public static int KMP(String str, String sub, int pos) {
// 判断两个串不能为空
if(str == null || sub == null) {
return -1;
}
int i = pos;// i遍历主串 从pos位置开始
int j = 0; // j遍历字串 从0开始
int strLength = str.length();
int subLength = sub.length();
if(strLength == 0 || subLength == 0) {
return -1;
}
// 判断pos位置合法性
if(pos < 0 || pos > strLength) {
return -1;
}
//求字串的next数组
int[] next = new int[subLength];
getNext(next,sub);
while(i < strLength && j < subLength) {
if(j == -1 || str.charAt(i) == sub.charAt(j)) {
i++;
j++;
}else {
j = next[j];
}
}if(j == subLength) {
// 字串遍历完之后 j应该等于sublength
// 找到返回字串在主串中的起始位置
return i - j;
}else {
// 找不到返回-1
return -1;
}
}
public static void main(String[] args) {
String str = "ababcabcdabcdefg";
String sub = "gba";
int pos = KMP(str,sub,0);
System.out.println(pos);
}
❗️❗️❗️需要注意,在KMP方法中:
while(i < strLength && j < subLength) {
if(j == -1 || str.charAt(i) == sub.charAt(j)) {
这里的 if 语句判断 j == -1 是为了: 如果子串第一个字符 "g" 就匹配失败
❌( main 方法里设置的子串就是这种情况)
👉会执行下面的 else 语句:j = next[ j ] ,而此时 next[ j ] = next[ 0 ] = -1 啊,所以 j 会被赋值为 -1
👉 再进入 while循环 时,正因为 if 判断条件中有 j == -1
,所以还要进入这个 if 语句
👉 进来之后 i 和 j 都加 1 ,仔细想一下,会发现:主串中的 i 已经向后走了一个,而 j 正好又回到子串的第一个字符 "g" 这里
,就这样在主串中找是否有一个字符和子串的当前 j 下标字符匹配
👉 i 一直在遍历主串,而 j 一直在 “g” 的位置,当主串遍历完后,匹配不到最终返回 -1;
总结
以上就是KMP算法的全部内容啦,主要有以下几个重点:
1,理解KMP算法的思想
2,next数组的计算( k 的值)
3,next[ 0 ] 和 next[ 1 ]
4,判断 j == -1 的情况
如果本篇对你有帮助,请点赞收藏支持一下,小手一抖就是对作者莫大的鼓励啦😋😋😋~
上山总比下山辛苦
下篇文章见
相关文章
- 一些优秀的小工具,快速帮助我们办公!
- 三线表制作(word)
- 苹果手机和Windows之间互传文件
- VmWare虚拟机和主机配置为同一网段IP
- IMX6ULL基本环境搭建
- 一个或多个C文件编译KO
- Linux设备驱动--异步通知
- Linux设备驱动--轮询操作
- Linux设备驱动--阻塞与非阻塞I/O
- Linux设备驱动中的并发控制
- Linux字符设备驱动学习
- Linux下编译生成SO并进行调用执行
- FreeRTOS-06-信号量
- FreeRTOS-04-内核控制函数+时间管理函数
- tensorflow语法【tf.concat()详解】
- C实现奇偶校验
- FreeRTOS-02-列表和列表项
- FreeRTOS-01-任务相关函数
- FreeRTOS-00-说明+基础知识
- C语言-使用malloc导致的奔溃问题