哈尔滨门户网站制作哪家好,硬件工程师,产品外观造型设计,自己怎么制作企业网站前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: #x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 #x1f4d9; Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 #x1f4d8; JavaE…前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新) 本篇为大家介绍KMP算法, 力求用最白话, 最通俗的文字让你学会KMP算法✌️ 提示是正在努力进步的小菜鸟一只如有大佬发现文章欠佳之处欢迎批评指点~ 废话不多说直接上干货 文章目录 前言一、KMP算法是什么二、解析KMP算法1.KMP 算法的思想2.next 数组核心2.1, next 数组的计算规则2.2, 新的变量 K2.3, 期望情况 : charAt( j-1 ) charAt( k )✅2.4, 非期望情况 : charAt( j-1 ) ! charAt( k )❎2.4, 分析 next[0] 和 next[1] 的取值 三、KMP算法完整代码总结 一、KMP算法是什么
KMP算法是一种改进的字符串匹配算法由D.E.KnuthJ.H.Morris和V.R.Pratt提出的因此人们称它为克努特—莫里斯—普拉特操作简称KMP算法。
KMP算法的核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现的核心就是通过一个 next()函数实现函数本身包含了模式串的局部匹配信息。 以上是百度百科的概念, 大概你是一脸懵逼, 没关系, 本篇一定让你学会 KMP
先看概念解释的第一句 : “KMP算法是一种改进的字符串匹配算法” 那么我们先了解一下最最最原始的 BF暴力匹配算法的过程 什么是字符串匹配 比如一个字符串“abcababcabc” 作为主串 要在这个主串中找到 “abcabc” , 则abcabc 被称作子串 利用 i 和 j 下标分别访问这两个字符串的字符 依次匹配, 直到在主串中找到完整的子串 BF算法过程简述 主串和当子串中的 “abcab” 匹配完之后, 发现下一个字符 “c” 和主串的下一个字符 “a” 不匹配 那么 BF 算法就直接将 j 移动到子串的起点, i 移动到主串的下一个字符处如图 用子串的第一个字符 “a” 去比较主串的下一个字符 “c” 虽然BF算法也可以实现字符串匹配, 但还有需要改进的地方
假设匹配子串时, 多次中途匹配失败, 每一次子串都需要从头再来, 这就是缺陷 举一个通俗的栗子: 你在跨栏比赛, 中途跨栏失败了一次, BF 算法就惩罚你, 让你从起点重新跑 而KMP算法会为你安排一个合适的惩罚, 可能是让你后退 2 米, 可能让你后退 20 米, 也有可能让你从头跑 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” ? 问题又来了, 蓝色方块和绿色方块是我肉眼找出来的, 那么程序是如何找到蓝色方块呢?
换句话说, 如何计算 next 数组的值? 接下来就要解析一下 next 数组的计算规则 2.1, 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 种情况才是理想的, 我们希望发生的如果发生第 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数组的长度为1return;}// 前提条件是数组长度大于1next[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 {// 找不到返回-1return -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 算法的全部内容啦, 主要有以下几个重点
理解 KMP 算法的思想next 数组的计算 k 的值next[ 0 ] 和 next[ 1 ]判断 j -1 的情况
如果本篇对你有帮助, 请点赞收藏支持一下, 小手一抖就是对作者莫大的鼓励啦~ 上山总比下山辛苦 下篇文章见
