KMP算法——通俗易懂讲好KMP算法：实例图解分析+详细代码注解 --》你的所有疑惑在本文都能得到解答_kmp算法例子-程序员宅基地
技术标签： # 算法思想分析 算法 c++ java c语言 数据结构
1.kmp算法基本介绍
- KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。
- Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由
Donald Knuth、Vaughan Pratt、James H. Morris三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。 - KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。
2.字符串的最长公共前后缀&部分匹配表
2.1 什么是最长公共前后缀
1️⃣ 字符串的前缀是指不包含最后一个字符的所有以第一个字符（索引为0）开头的连续子串
比如字符串 “ABABA” 的前缀有：A，AB，ABA，ABAB
2️⃣ 字符串的后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
比如字符串 “ABABA” 的后缀有：BABA，ABA，BA，A
3️⃣ 公共前后缀：一个字符串的 所有前缀连续子串 和 所有后缀连续子串 中相等的子串
比如字符串 “ABABA”
- 前缀有：A，AB，ABA，ABAB
- 后缀有：BABA，ABA，BA，A
因此公共前后缀有：A ，ABA
4️⃣ 最长公共前后缀：所有公共前后缀 的 长度最长的 那个子串
比如字符串 “ABABA” ，公共前后缀有：A ，ABA
由于
ABA是 三个字符长度，A是一个字符长度，那么最长公共前后缀就是 ABA
再比如说一个字符串 str = “ABCABD”
-
对于str从
索引为0开始的子串 “A” 而言：- 前缀：不包含
最后一个字符A的 所有以第一个字符A开头 的 连续子串 不存在 - 后缀：不包含
第一个字符A的 所有以最后一个字符A结尾 的 连续子串 不存在
因此该子串的最长公共前后缀 为 0
- 前缀：不包含
-
对于str从 索引为0 开始的子串 “
AB” 而言：- 前缀：不包含
最后一个字符B的 所有以第一个字符A开头 的 连续子串 有 —— “A” - 后缀：不包含
第一个字符A的 所有以最后一个字符B结尾 的 连续子串 有 —— “B”
因此该子串的最长公共前后缀 为 0
- 前缀：不包含
-
对于str从 索引为0 开始的子串 “
ABC” 而言：- 前缀：不包含
最后一个字符C的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB” - 后缀：不包含
第一个字符A的 所有以最后一个字符C结尾 的 连续子串有 —— “BC”，“C”
前缀与后缀的连续子串不存在相同的，因此该子串的最长公共前后缀 为 0
- 前缀：不包含
-
对于str从 索引为0 开始的子串 “
ABCA” 而言：- 前缀：不包含
最后一个字符A的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”，“ABC” - 后缀：不包含
第一个字符A的 所有以最后一个字符A结尾 的 连续子串有 —— “BCA”，“CA”，“A”
前缀与后缀的连续子串中存在相同且最长的子串 A，因此该子串的最长公共前后缀 为 1
- 前缀：不包含
-
对于str从 索引为0 开始的子串 “
ABCAB” 而言：- 前缀：不包含
最后一个字符B的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”，“ABC”，“ABCA” - 后缀：不包含
第一个字符A的 所有以最后一个字符B结尾 的 连续子串有 —— “BCAB”，“CAB”，“AB”，“B”
前缀与后缀的连续子串中存在相同且最长的子串 AB，因此该子串的最长公共前后缀 为 2
- 前缀：不包含
-
对于str从 索引为0 开始的子串 “
ABCABD” 而言：- 前缀：不包含
最后一个字符D的 所有以第一个字符A开头 的 连续子串 有 —— “A”，“AB”，“ABC”，“ABCA”，“ABCAB” - 后缀：不包含
第一个字符A的 所有以最后一个字符D结尾 的 连续子串有 —— “BCABD”，“CABD”，“ABD”，“BD”，“D”
前缀与后缀的连续子串不存在相同的，因此该子串的最长公共前后缀 为 0
- 前缀：不包含
2.2 什么是部分匹配表Next
个人理解：对于字符串str，从 第一个字符开始的每个子串 的 最后一个字符 与 该子串的最长公共前后缀的长度 的对应关系表格。这个表我们以 int[] next 数组方式进行存储。
比如说上面举的例子：
- 子串 “
A”：最后一个字符是 A，该子串的最长公共前后缀长度是 0，因此对应关系就是 A - 0 - 子串 “
AB”：最后一个字符是 B，该子串的最长公共前后缀长度是 0，因此对应关系就是 B - 0 - 子串 “
ABC”：最后一个字符是 C，该子串的最长公共前后缀长度是 0，因此对应关系就是 C - 0 - 子串 “
ABCA”：最后一个字符是 A，该子串的最长公共前后缀长度是 1，因此对应关系就是 A - 1 - 子串 “
ABCAB”：最后一个字符是 B，该子串的最长公共前后缀长度是 2，因此对应关系就是 B - 2 - 子串 “
ABCABD”：最后一个字符是 D，该子串的最长公共前后缀长度是 0，因此对应关系就是 D - 0
因此综上，我们说该字符串 str 的部分匹配表为：
| A | B | C | A | B | D |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 2 | 0 |
那么对应的next数组就是 int[] next = {0, 0, 0, 1, 2, 0}
2.3 字符串最长公共前后缀&部分匹配表的代码实现
下面的代码可以参考图中实例进行分析：
/**
* 获取一个字符串 pattern 的部分匹配表
*
* @param patternStr 用于模式匹配字符串
* @return 存储部分匹配表的每个子串的最长公共前后缀的 next数组
*/
public static int[] kmpNext(String patternStr) {
//将 patternStr 转为 字符数组形式
char[] patternArr = patternStr.toCharArray();
//预先创建一个next数组，用于存储部分匹配表的每个子串的最长公共前后缀
int[] next = new int[patternStr.length()];
/*
从第一个字符（对应索引为0）开始的子串，如果子串的长度为1，那么肯定最长公共前后缀为0
因为这唯一的一个字符既是第一个字符，又是最后一个字符，所以前后缀都不存在 -> 最长公共前后缀为0
*/
next[0] = 0;
/*
len有两个作用：
1. 用于记录当前子串的最长公共前后缀长度
2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1]/当前子串最长公共前缀字符串的下一个字符的索引 <-- 可以拿示例分析一下
*/
int len = 0;
//从第二个字符开始遍历，求索引在 [0,i] 的子串的最长公共前后缀长度
int i = 1;
while (i < patternArr.length) {
/*
1.已经知道了上一个子串 对应索引[0,i-1] 的最长公共前后缀长度为 len
的前缀字符串是 索引[0,len-1]，对应相等的后缀字符串是 索引[i-len,i-1]
2.因此我们可以以 上一个子串的最长公共前后缀字符串 作为拼接参考
比较一下 patternArr[len] 与 patternArr[i] 是否相等
*/
if (patternArr[len] == patternArr[i]) {
/*
1.如果相等即 patternArr[len]==patternArr[i]，
那么就可以确定当前子串的最长公共前后缀的
前缀字符串是 索引[0,len] ，对应相等的后缀字符串是 索引[i-len,i]
2.由于是拼接操作，那么当前子串的最长公共前后缀长度只需要在上一个子串的最长公共前后缀长度的基础上 +1 即可
即 next[i] = next[i-1] + 1 ，
3.由于 len 是记录的子串的最长公共前后缀长度，对于当前我们所在的代码位置而言
len 还是记录的上一个子串的最长公共前后缀长度，因此：
next[i] = next[i-1] + 1 等价于 next[i] = ++len
*/
// 等价于 next[i] = next[i-1] + 1
next[i] = ++len;
//既然找到了索引在[0,i]的子串的最长公共前后缀字符串长度，那就 i+1 去判断以下一个字符结尾的子串的最长公共前后缀长度
i++;
}else {
/*
1.如果不相等 patternArr[len]!=patternArr[i]
我们想要求当前子串 对应索引[0,i] 的最长公共前后缀长度
我们就不能以 上一个子串的最长公共前后缀：前缀字符串pre 后缀字符串post （毫无疑问pre==post） 作为拼接参考
2.但可以思考一下：
pre的最长公共前缀字符串： 索引 [ 0 , next[len-1] )
是等于
post的最长公共后缀字符串：索引 [ i-next[len-1] , i )
则我们 就以 pre的最长公共前缀字符串/post的最长公共后缀字符串 作为拼接参考
去判断 pre的最长公共前缀字符串的下一个字符patternArr[next[len-1]] 是否等于 post的最长公共后缀字符串的下一个字符patternArr[i]
3.在第 1,2 步分析的基础上
我们可以在判断出 patternArr[len]!=patternArr[i] 后，
不去执行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
可以先修改len的值：len = next[len-1]，len就成了 pre的最长公共前缀字符串长度/post的最长公共后缀字符串长度，
修改完之后，再去判断下一个字符 是否相等，即 判断 patternArr[len] 是否等于 patternArr[i]
仔细观察，这不又是在判断 这个循环中 if-else 语句吗
4.关于 len 这个值，在循环开始时我们解释的是：上一个子串的最长公共前后缀字符串的长度
但实际上我们在这里改为 len = next[len-1] 表示上一个子串的最长公共前后缀字符串的最长公共前后缀字符串的长度
是没有问题的，等价于上一个子串的较小的公共前后缀字符串。
既然进入了 else 语句说明字符不相等，就不能以 上一个子串的最长公共前后缀字符串 作为 拼接参考，就应当去缩小参考范围。
*/
if(len==0) {
/*
len为0说明上一个子串已经没有了公共前后缀字符串
则我们没有继续寻找的必要 --> 索引在[0, i]的当前子串的最长公共前后缀字符串长度就是0
*/
next[i] = len;
//继续寻找下一个字符串的最长公共前后缀字符串长度
i++;
}else{
len = next[len - 1];
}
}
}
return next;
}
2.4 代码测试
package kmp;
import java.util.Arrays;
/**
* @author 狐狸半面添
* @create 2022-11-22 22:43
*/
public class KMPAlgorithm {
public static void main(String[] args) {
String patternStr = "ABCDABD";
//输出结果：[0, 0, 0, 0, 1, 2, 0]
System.out.println(Arrays.toString(kmpNext(str2)));
}
/**
* 获取一个字符串 pattern 的部分匹配表
*
* @param patternStr 用于模式匹配字符串
* @return 存储部分匹配表的每个子串的最长公共前后缀的 next数组
*/
public static int[] kmpNext(String patternStr) {
//将 patternStr 转为 字符数组形式
char[] patternArr = patternStr.toCharArray();
//预先创建一个next数组，用于存储部分匹配表的每个子串的最长公共前后缀
int[] next = new int[patternStr.length()];
/*
从第一个字符（对应索引为0）开始的子串，如果子串的长度为1，那么肯定最长公共前后缀为0
因为这唯一的一个字符既是第一个字符，又是最后一个字符，所以前后缀都不存在 -> 最长公共前后缀为0
*/
next[0] = 0;
/*
len有两个作用：
1. 用于记录当前子串的最长公共前后缀长度
2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1]/当前子串最长公共前缀字符串的下一个字符的索引 <-- 可以拿示例分析一下
*/
int len = 0;
//从第二个字符开始遍历，求索引在 [0,i] 的子串的最长公共前后缀长度
int i = 1;
while (i < patternArr.length) {
/*
1.已经知道了上一个子串 对应索引[0,i-1] 的最长公共前后缀长度为 len
的前缀字符串是 索引[0,len-1]，对应相等的后缀字符串是 索引[i-len,i-1]
2.因此我们可以以 上一个子串的最长公共前后缀字符串 作为拼接参考
比较一下 patternArr[len] 与 patternArr[i] 是否相等
*/
if (patternArr[len] == patternArr[i]) {
/*
1.如果相等即 patternArr[len]==patternArr[i]，
那么就可以确定当前子串的最长公共前后缀的
前缀字符串是 索引[0,len] ，对应相等的后缀字符串是 索引[i-len,i]
2.由于是拼接操作，那么当前子串的最长公共前后缀长度只需要在上一个子串的最长公共前后缀长度的基础上 +1 即可
即 next[i] = next[i-1] + 1 ，
3.由于 len 是记录的子串的最长公共前后缀长度，对于当前我们所在的代码位置而言
len 还是记录的上一个子串的最长公共前后缀长度，因此：
next[i] = next[i-1] + 1 等价于 next[i] = ++len
*/
// 等价于 next[i] = next[i-1] + 1
next[i] = ++len;
//既然找到了索引在[0,i]的子串的最长公共前后缀字符串长度，那就 i+1 去判断以下一个字符结尾的子串的最长公共前后缀长度
i++;
}else {
/*
1.如果不相等 patternArr[len]!=patternArr[i]
我们想要求当前子串 对应索引[0,i] 的最长公共前后缀长度
我们就不能以 上一个子串的最长公共前后缀：前缀字符串pre 后缀字符串post （毫无疑问pre==post） 作为拼接参考
2.但可以思考一下：
pre的最长公共前缀字符串： 索引 [ 0 , next[len-1] )
是等于
post的最长公共后缀字符串：索引 [ i-next[len-1] , i )
则我们 就以 pre的最长公共前缀字符串/post的最长公共后缀字符串 作为拼接参考
去判断 pre的最长公共前缀字符串的下一个字符patternArr[next[len-1]] 是否等于 post的最长公共后缀字符串的下一个字符patternArr[i]
3.在第 1,2 步分析的基础上
我们可以在判断出 patternArr[len]!=patternArr[i] 后，
不去执行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
可以先修改len的值：len = next[len-1]，len就成了 pre的最长公共前缀字符串长度/post的最长公共后缀字符串长度，
修改完之后，再去判断下一个字符 是否相等，即 判断 patternArr[len] 是否等于 patternArr[i]
仔细观察，这不又是在判断 这个循环中 if-else 语句吗
4.关于 len 这个值，在循环开始时我们解释的是：上一个子串的最长公共前后缀字符串的长度
但实际上我们在这里改为 len = next[len-1] 表示上一个子串的最长公共前后缀字符串的最长公共前后缀字符串的长度
是没有问题的，等价于上一个子串的较小的公共前后缀字符串。
既然进入了 else 语句说明字符不相等，就不能以 上一个子串的最长公共前后缀字符串 作为 拼接参考，就应当去缩小参考范围。
*/
if(len==0) {
/*
len为0说明上一个子串已经没有了公共前后缀字符串
则我们没有继续寻找的必要 --> 索引在[0, i]的当前子串的最长公共前后缀字符串长度就是0
*/
next[i] = len;
//继续寻找下一个字符串的最长公共前后缀字符串长度
i++;
}else{
len = next[len - 1];
}
}
}
return next;
}
}
3.根据部分匹配表搜索字符串匹配位置
3.1 匹配成功一个就退出匹配的代码
3.1.1 KMP算法的大致步骤
-
求出
模式字符串patternStr的部分匹配表，已知待匹配的字符串matchStr -
定义两个指针
i和j，分别指向 patternStr 和 matchStr ，初始化为0 -
判断 patternStr[i] 和 matchStr[j] 是否相等
-
如果相等，则继续向后匹配：i++, j++
-
如果不相等，则 i 不变，调整 j 为 模式字符串pattern 的 上一个子串（索引 [ 0, j-1 ]）的最长公共
前缀字符串的下一个索引位置，该索引位置也是最长公共前缀/后缀字符串的长度：j = next[ j - 1 ]解释一下不相等为什么要这样做：
1️⃣ 在不相等的时候，我们可以知道前面已经匹配的字符串
str1和str2肯定是完全相等的- str1：在 matchStr 中对应索引 [ i - j , i - 1 ]
- str2：在 patternStr 中对应索引 [ 0 , j - 1 ]
2️⃣ 由于 完全相等，则 str1 的 最长公共后缀字符串 一定等于 str2 的 最长公共前缀字符串，那么：
- 将 i 定位到 str1 的 最长公共后缀字符串 的 下一个字符位置，但很明显，i 此时的位置肯定已经是在 str1 的最长公共后缀字符串的下一个字符的位置，因此 i 的值不需要做调整
- 将 j 定位到 str2 的 最长公共前缀字符串 的 下一个字符位置 ，next [ j - 1] 不仅代表 上一个子串str1的最长公共前后缀字符串长度，也是最长公共前缀字符串的下一个字符的索引。因此，我们只需要：j = next[ j - 1 ]
3️⃣ 修改完毕，我们此时已经匹配的字符串：
- 在 matchStr 中 对应索引 [ i - j , i - 1 ]
- 在 patternStr 中 对应索引 [ 0 , j - 1 ]
4️⃣ 那么我们再继续比较已经匹配的字符串后面的字符就可以了，即 判断 patternStr[i] 和 matchStr[j] 是否相等，这又回到了 步骤三！！！
-
-
判断 i 和 j 是否超出 各自的最大索引值
- 如果都没到超出 各自最大索引值，就继续执行第三步进行比较（说明是个循环）
- 如果至少有一个超出了 各自最大索引值，就退出循环
-
循环结束后，判断 j 是否超出了 模式字符串的最大索引值
- 如果超出了，说明匹配成功，返回 patternStr 字符串匹配到的 matchStr 的第一个字符串的起始索引位置：i - j
- 如果没有超出，说明匹配失败，返回 -1 表示没有匹配到
3.1.2 代码实现+测试
package kmp;
import java.util.Arrays;
/**
* @author 狐狸半面添
* @create 2022-11-22 22:43
*/
public class KMPAlgorithm {
public static void main(String[] args) {
String matchStr = "AABABADDABAC";
String patternStr = "ABA";
// 输出：index = 1
System.out.println("index = " + kmpSearch(matchStr, patternStr, kmpNext(patternStr)));
}
/**
* kmp搜索算法
*
* @param matchStr 原字符串
* @param patternStr 子串
* @param next 子串对应的部分匹配表
* @return 如果是-1，就是没有匹配到，否则就返回第一个匹配的位置
*/
public static int kmpSearch(String matchStr, String patternStr, int[] next) {
int i = 0, j = 0;
while (i < matchStr.length() && j < patternStr.length()) {
if (matchStr.charAt(i) == patternStr.charAt(j)) {
//相等就继续进行匹配
i++;
j++;
} else {
//如果 patternStr[i] 和 matchStr[j] 不相等
if (j == 0) {
/*
表示 matchStr 没有匹配到 patternStr的第一个字符
那直接将 matchStr 的指针 i 向后移动一位即可
*/
i++;
} else {
j = next[j - 1];
}
}
}
return j == patternStr.length() ? i - j : -1;
}
/**
* 获取一个字符串 pattern 的部分匹配表
*
* @param patternStr 用于模式匹配字符串
* @return 存储部分匹配表的每个子串的最长公共前后缀的 next数组
*/
public static int[] kmpNext(String patternStr) {
//将 patternStr 转为 字符数组形式
char[] patternArr = patternStr.toCharArray();
//预先创建一个next数组，用于存储部分匹配表的每个子串的最长公共前后缀
int[] next = new int[patternStr.length()];
/*
从第一个字符（对应索引为0）开始的子串，如果子串的长度为1，那么肯定最长公共前后缀为0
因为这唯一的一个字符既是第一个字符，又是最后一个字符，所以前后缀都不存在 -> 最长公共前后缀为0
*/
next[0] = 0;
/*
len有两个作用：
1. 用于记录当前子串的最长公共前后缀长度
2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1] <-- 可以拿示例分析一下
*/
int len = 0;
//从第二个字符开始遍历，求索引在 [0,i] 的子串的最长公共前后缀长度
int i = 1;
while (i < patternArr.length) {
/*
1.已经知道了上一个子串 对应索引[0,i-1] 的最长公共前后缀长度为 len
的前缀字符串是 索引[0,len-1]，对应相等的后缀字符串是 索引[i-len,i-1]
2.因此我们可以以 上一个子串的最长公共前后缀字符串 作为拼接参考
比较一下 patternArr[len] 与 patternArr[i] 是否相等
*/
if (patternArr[len] == patternArr[i]) {
/*
1.如果相等即 patternArr[len]==patternArr[i]，
那么就可以确定当前子串的最长公共前后缀的
前缀字符串是 索引[0,len] ，对应相等的后缀字符串是 索引[i-len,i]
2.由于是拼接操作，那么当前子串的最长公共前后缀长度只需要在上一个子串的最长公共前后缀长度的基础上 +1 即可
即 next[i] = next[i-1] + 1 ，
3.由于 len 是记录的子串的最长公共前后缀长度，对于当前我们所在的代码位置而言
len 还是记录的上一个子串的最长公共前后缀长度，因此：
next[i] = next[i-1] + 1 等价于 next[i] = ++len
*/
// 等价于 next[i] = next[i-1] + 1
next[i] = ++len;
//既然找到了索引在[0,i]的子串的最长公共前后缀字符串长度，那就 i+1 去判断以下一个字符结尾的子串的最长公共前后缀长度
i++;
} else {
/*
1.如果不相等 patternArr[len]!=patternArr[i]
我们想要求当前子串 对应索引[0,i] 的最长公共前后缀长度
我们就不能以 上一个子串的最长公共前后缀：前缀字符串pre 后缀字符串post （毫无疑问pre==post） 作为拼接参考
2.但可以思考一下：
pre的最长公共前缀字符串： 索引 [ 0 , next[len-1] )
是等于
post的最长公共后缀字符串：索引 [ i-next[len-1] , i )
则我们 就以 pre的最长公共前缀字符串/post的最长公共后缀字符串 作为拼接参考
去判断 pre的最长公共前缀字符串的下一个字符patternArr[next[len-1]] 是否等于 post的最长公共后缀字符串的下一个字符patternArr[i]
3.在第 1,2 步分析的基础上
我们可以在判断出 patternArr[len]!=patternArr[i] 后，
不去执行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
可以先修改len的值：len = next[len-1]，len就成了 pre的最长公共前缀字符串长度/post的最长公共后缀字符串长度，
修改完之后，再去判断下一个字符 是否相等，即 判断 patternArr[len] 是否等于 patternArr[i]
仔细观察，这不又是在判断 这个循环中 if-else 语句吗
4.关于 len 这个值，在循环开始时我们解释的是：上一个子串的最长公共前后缀字符串的长度
但实际上我们在这里改为 len = next[len-1] 表示上一个子串的最长公共前后缀字符串的最长公共前后缀字符串的长度
是没有问题的，等价于上一个子串的较小的公共前后缀字符串。
既然进入了 else 语句说明字符不相等，就不能以 上一个子串的最长公共前后缀字符串 作为 拼接参考，就应当去缩小参考范围。
*/
if (len == 0) {
/*
len为0说明上一个子串已经没有了公共前后缀字符串
则我们没有继续寻找的必要 --> 索引在[0, i]的当前子串的最长公共前后缀字符串长度就是0
*/
next[i] = len;
//继续寻找下一个字符串的最长公共前后缀字符串长度
i++;
} else {
len = next[len - 1];
}
}
}
return next;
}
}
3.2 允许匹配多个，可重复索引字符的代码
3.2.1 KMP算法的大致步骤
- 求出
模式字符串patternStr的部分匹配表，已知待匹配的字符串matchStr - 定义两个指针
i和j，分别指向 patternStr 和 matchStr ，初始化为0 - 定义一个 ArrayList 集合
firstIndexList，用于存储每次匹配成功的字符串的开始索引位置 - 判断 patternStr[i] 和 matchStr[j] 是否相等
- 如果相等，则继续向后匹配：i++, j++
- 如果不相等，则 i 不变，调整 j 为 模式字符串pattern 的 上一个子串（索引 [ 0, j-1 ]）的最长公共
前缀字符串的下一个索引位置，该索引位置也是最长公共前缀/后缀字符串的长度：j = next[ j - 1 ]
- 判断 i 是否超出 最大索引值
- 如果超出了 matchStr 的 最大索引值，就退出循环
- 判断 j 是否超出了 最大索引值
- 如果超出了 patternStr 的最大索引值：
- 将匹配到的字符串的开始索引位置加入到
firstIndexList集合：firstIndexList.add( i - j ) - 调整 j 为 模式字符串pattern （索引 [ 0, j-1 ]）的最长公共
前缀字符串的下一个索引位置，该索引位置也是最长公共前缀/后缀字符串的长度：j = next[ j - 1 ]。
- 将匹配到的字符串的开始索引位置加入到
- 如果超出了 patternStr 的最大索引值：
- 第五步成立则循环退出，返回
firstIndexList集合
3.2.2 代码实现+测试
package kmp;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author 狐狸半面添
* @create 2022-11-22 22:43
*/
public class KMPAlgorithm {
public static void main(String[] args) {
String matchStr = "AABABADDABAC";
String patternStr = "ABA";
// 输出：[1, 3, 8]
System.out.println(kmpSearch(matchStr, patternStr, kmpNext(patternStr)).toString());
}
/**
* kmp搜索算法
*
* @param matchStr 原字符串
* @param patternStr 子串
* @param next 子串对应的部分匹配表
* @return 每次匹配成功的字符串的开始索引位置的集合
*/
public static ArrayList<Integer> kmpSearch(String matchStr, String patternStr, int[] next) {
int i = 0, j = 0;
ArrayList<Integer> firstIndexList = new ArrayList<>();
while (i < matchStr.length()) {
if (matchStr.charAt(i) == patternStr.charAt(j)) {
//相等就继续进行匹配
i++;
j++;
} else {
//如果 patternStr[i] 和 matchStr[j] 不相等
if (j == 0) {
/*
表示 matchStr 没有匹配到 patternStr的第一个字符
那直接将 matchStr 的指针 i 向后移动一位即可
*/
i++;
} else {
j = next[j - 1];
}
}
if (j == patternStr.length()) {
//超出了最大索引值
firstIndexList.add(i - j);
j = next[j - 1];
}
}
return firstIndexList;
}
/**
* 获取一个字符串 pattern 的部分匹配表
*
* @param patternStr 用于模式匹配字符串
* @return 存储部分匹配表的每个子串的最长公共前后缀的 next数组
*/
public static int[] kmpNext(String patternStr) {
//将 patternStr 转为 字符数组形式
char[] patternArr = patternStr.toCharArray();
//预先创建一个next数组，用于存储部分匹配表的每个子串的最长公共前后缀
int[] next = new int[patternStr.length()];
/*
从第一个字符（对应索引为0）开始的子串，如果子串的长度为1，那么肯定最长公共前后缀为0
因为这唯一的一个字符既是第一个字符，又是最后一个字符，所以前后缀都不存在 -> 最长公共前后缀为0
*/
next[0] = 0;
/*
len有两个作用：
1. 用于记录当前子串的最长公共前后缀长度
2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1] <-- 可以拿示例分析一下
*/
int len = 0;
//从第二个字符开始遍历，求索引在 [0,i] 的子串的最长公共前后缀长度
int i = 1;
while (i < patternArr.length) {
/*
1.已经知道了上一个子串 对应索引[0,i-1] 的最长公共前后缀长度为 len
的前缀字符串是 索引[0,len-1]，对应相等的后缀字符串是 索引[i-len,i-1]
2.因此我们可以以 上一个子串的最长公共前后缀字符串 作为拼接参考
比较一下 patternArr[len] 与 patternArr[i] 是否相等
*/
if (patternArr[len] == patternArr[i]) {
/*
1.如果相等即 patternArr[len]==patternArr[i]，
那么就可以确定当前子串的最长公共前后缀的
前缀字符串是 索引[0,len] ，对应相等的后缀字符串是 索引[i-len,i]
2.由于是拼接操作，那么当前子串的最长公共前后缀长度只需要在上一个子串的最长公共前后缀长度的基础上 +1 即可
即 next[i] = next[i-1] + 1 ，
3.由于 len 是记录的子串的最长公共前后缀长度，对于当前我们所在的代码位置而言
len 还是记录的上一个子串的最长公共前后缀长度，因此：
next[i] = next[i-1] + 1 等价于 next[i] = ++len
*/
// 等价于 next[i] = next[i-1] + 1
next[i] = ++len;
//既然找到了索引在[0,i]的子串的最长公共前后缀字符串长度，那就 i+1 去判断以下一个字符结尾的子串的最长公共前后缀长度
i++;
} else {
/*
1.如果不相等 patternArr[len]!=patternArr[i]
我们想要求当前子串 对应索引[0,i] 的最长公共前后缀长度
我们就不能以 上一个子串的最长公共前后缀：前缀字符串pre 后缀字符串post （毫无疑问pre==post） 作为拼接参考
2.但可以思考一下：
pre的最长公共前缀字符串： 索引 [ 0 , next[len-1] )
是等于
post的最长公共后缀字符串：索引 [ i-next[len-1] , i )
则我们 就以 pre的最长公共前缀字符串/post的最长公共后缀字符串 作为拼接参考
去判断 pre的最长公共前缀字符串的下一个字符patternArr[next[len-1]] 是否等于 post的最长公共后缀字符串的下一个字符patternArr[i]
3.在第 1,2 步分析的基础上
我们可以在判断出 patternArr[len]!=patternArr[i] 后，
不去执行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
可以先修改len的值：len = next[len-1]，len就成了 pre的最长公共前缀字符串长度/post的最长公共后缀字符串长度，
修改完之后，再去判断下一个字符 是否相等，即 判断 patternArr[len] 是否等于 patternArr[i]
仔细观察，这不又是在判断 这个循环中 if-else 语句吗
4.关于 len 这个值，在循环开始时我们解释的是：上一个子串的最长公共前后缀字符串的长度
但实际上我们在这里改为 len = next[len-1] 表示上一个子串的最长公共前后缀字符串的最长公共前后缀字符串的长度
是没有问题的，等价于上一个子串的较小的公共前后缀字符串。
既然进入了 else 语句说明字符不相等，就不能以 上一个子串的最长公共前后缀字符串 作为 拼接参考，就应当去缩小参考范围。
*/
if (len == 0) {
/*
len为0说明上一个子串已经没有了公共前后缀字符串
则我们没有继续寻找的必要 --> 索引在[0, i]的当前子串的最长公共前后缀字符串长度就是0
*/
next[i] = len;
//继续寻找下一个字符串的最长公共前后缀字符串长度
i++;
} else {
len = next[len - 1];
}
}
}
return next;
}
}
3.3 允许匹配多个，不可重复索引字符的代码
3.3.1 KMP算法的大致步骤
- 求出
模式字符串patternStr的部分匹配表，已知待匹配的字符串matchStr - 定义两个指针
i和j，分别指向 patternStr 和 matchStr ，初始化为0 - 定义一个 ArrayList 集合
firstIndexList，用于存储每次匹配成功的字符串的开始索引位置 - 判断 patternStr[i] 和 matchStr[j] 是否相等
- 如果相等，则继续向后匹配：i++, j++
- 如果不相等，则 i 不变，调整 j 为 模式字符串pattern 的 上一个子串（索引 [ 0, j-1 ]）的最长公共
前缀字符串的下一个索引位置，该索引位置也是最长公共前缀/后缀字符串的长度：j = next[ j - 1 ]
- 判断 i 是否超出 最大索引值
- 如果超出了 matchStr 的 最大索引值，就退出循环
- 判断 j 是否超出了 最大索引值
- 如果超出了 patternStr 的最大索引值：
- 将匹配到的字符串的开始索引位置加入到
firstIndexList集合：firstIndexList.add( i - j ) - 设置 j = 0 开始重新匹配
- 将匹配到的字符串的开始索引位置加入到
- 如果超出了 patternStr 的最大索引值：
- 第五步成立则循环退出，返回
firstIndexList集合
3.3.2 代码实现+测试
package kmp;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author 狐狸半面添
* @create 2022-11-22 22:43
*/
public class KMPAlgorithm {
public static void main(String[] args) {
String matchStr = "AABABADDABAC";
String patternStr = "ABA";
// 输出：[1, 8]
System.out.println(kmpSearch(matchStr, patternStr, kmpNext(patternStr)).toString());
}
/**
* kmp搜索算法
*
* @param matchStr 原字符串
* @param patternStr 子串
* @param next 子串对应的部分匹配表
* @return 每次匹配成功的字符串的开始索引位置的集合
*/
public static ArrayList<Integer> kmpSearch(String matchStr, String patternStr, int[] next) {
int i = 0, j = 0;
ArrayList<Integer> firstIndexList = new ArrayList<>();
while (i < matchStr.length()) {
if (matchStr.charAt(i) == patternStr.charAt(j)) {
//相等就继续进行匹配
i++;
j++;
} else {
//如果 patternStr[i] 和 matchStr[j] 不相等
if (j == 0) {
/*
表示 matchStr 没有匹配到 patternStr的第一个字符
那直接将 matchStr 的指针 i 向后移动一位即可
*/
i++;
} else {
j = next[j - 1];
}
}
if (j == patternStr.length()) {
//超出了最大索引值
firstIndexList.add(i - j);
j = 0;
}
}
return firstIndexList;
}
/**
* 获取一个字符串 pattern 的部分匹配表
*
* @param patternStr 用于模式匹配字符串
* @return 存储部分匹配表的每个子串的最长公共前后缀的 next数组
*/
public static int[] kmpNext(String patternStr) {
//将 patternStr 转为 字符数组形式
char[] patternArr = patternStr.toCharArray();
//预先创建一个next数组，用于存储部分匹配表的每个子串的最长公共前后缀
int[] next = new int[patternStr.length()];
/*
从第一个字符（对应索引为0）开始的子串，如果子串的长度为1，那么肯定最长公共前后缀为0
因为这唯一的一个字符既是第一个字符，又是最后一个字符，所以前后缀都不存在 -> 最长公共前后缀为0
*/
next[0] = 0;
/*
len有两个作用：
1. 用于记录当前子串的最长公共前后缀长度
2. 同时知道当前子串的最长公共前后缀的前缀字符串对应索引 [0,len-1] <-- 可以拿示例分析一下
*/
int len = 0;
//从第二个字符开始遍历，求索引在 [0,i] 的子串的最长公共前后缀长度
int i = 1;
while (i < patternArr.length) {
/*
1.已经知道了上一个子串 对应索引[0,i-1] 的最长公共前后缀长度为 len
的前缀字符串是 索引[0,len-1]，对应相等的后缀字符串是 索引[i-len,i-1]
2.因此我们可以以 上一个子串的最长公共前后缀字符串 作为拼接参考
比较一下 patternArr[len] 与 patternArr[i] 是否相等
*/
if (patternArr[len] == patternArr[i]) {
/*
1.如果相等即 patternArr[len]==patternArr[i]，
那么就可以确定当前子串的最长公共前后缀的
前缀字符串是 索引[0,len] ，对应相等的后缀字符串是 索引[i-len,i]
2.由于是拼接操作，那么当前子串的最长公共前后缀长度只需要在上一个子串的最长公共前后缀长度的基础上 +1 即可
即 next[i] = next[i-1] + 1 ，
3.由于 len 是记录的子串的最长公共前后缀长度，对于当前我们所在的代码位置而言
len 还是记录的上一个子串的最长公共前后缀长度，因此：
next[i] = next[i-1] + 1 等价于 next[i] = ++len
*/
// 等价于 next[i] = next[i-1] + 1
next[i] = ++len;
//既然找到了索引在[0,i]的子串的最长公共前后缀字符串长度，那就 i+1 去判断以下一个字符结尾的子串的最长公共前后缀长度
i++;
} else {
/*
1.如果不相等 patternArr[len]!=patternArr[i]
我们想要求当前子串 对应索引[0,i] 的最长公共前后缀长度
我们就不能以 上一个子串的最长公共前后缀：前缀字符串pre 后缀字符串post （毫无疑问pre==post） 作为拼接参考
2.但可以思考一下：
pre的最长公共前缀字符串： 索引 [ 0 , next[len-1] )
是等于
post的最长公共后缀字符串：索引 [ i-next[len-1] , i )
则我们 就以 pre的最长公共前缀字符串/post的最长公共后缀字符串 作为拼接参考
去判断 pre的最长公共前缀字符串的下一个字符patternArr[next[len-1]] 是否等于 post的最长公共后缀字符串的下一个字符patternArr[i]
3.在第 1,2 步分析的基础上
我们可以在判断出 patternArr[len]!=patternArr[i] 后，
不去执行第二步：patternArr[next[len-1]] 是否等于 patternArr[i]，
可以先修改len的值：len = next[len-1]，len就成了 pre的最长公共前缀字符串长度/post的最长公共后缀字符串长度，
修改完之后，再去判断下一个字符 是否相等，即 判断 patternArr[len] 是否等于 patternArr[i]
仔细观察，这不又是在判断 这个循环中 if-else 语句吗
4.关于 len 这个值，在循环开始时我们解释的是：上一个子串的最长公共前后缀字符串的长度
但实际上我们在这里改为 len = next[len-1] 表示上一个子串的最长公共前后缀字符串的最长公共前后缀字符串的长度
是没有问题的，等价于上一个子串的较小的公共前后缀字符串。
既然进入了 else 语句说明字符不相等，就不能以 上一个子串的最长公共前后缀字符串 作为 拼接参考，就应当去缩小参考范围。
*/
if (len == 0) {
/*
len为0说明上一个子串已经没有了公共前后缀字符串
则我们没有继续寻找的必要 --> 索引在[0, i]的当前子串的最长公共前后缀字符串长度就是0
*/
next[i] = len;
//继续寻找下一个字符串的最长公共前后缀字符串长度
i++;
} else {
len = next[len - 1];
}
}
}
return next;
}
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
class和struct的区别-程序员宅基地
文章浏览阅读101次。4.class可以有⽆参的构造函数，struct不可以，必须是有参的构造函数，⽽且在有参的构造函数必须初始。2.Struct适⽤于作为经常使⽤的⼀些数据组合成的新类型，表示诸如点、矩形等主要⽤来存储数据的轻量。1.Class⽐较适合⼤的和复杂的数据，表现抽象和多级别的对象层次时。2.class允许继承、被继承，struct不允许，只能继承接⼝。3.Struct有性能优势，Class有⾯向对象的扩展优势。3.class可以初始化变量，struct不可以。1.class是引⽤类型，struct是值类型。
android使用json后闪退,应用闪退问题：从json信息的解析开始就会闪退-程序员宅基地
文章浏览阅读586次。想实现的功能是点击顶部按钮之后按关键字进行搜索，已经可以从服务器收到反馈的json信息，但从json信息的解析开始就会闪退，加载listview也不知道行不行public abstract class loadlistview{public ListView plv;public String js;public int listlength;public int listvisit;public..._rton转json为什么会闪退
如何使用wordnet词典，得到英文句子的同义句_get_synonyms wordnet-程序员宅基地
文章浏览阅读219次。如何使用wordnet词典，得到英文句子的同义句_get_synonyms wordnet
系统项目报表导出功能开发_积木报表 多线程-程序员宅基地
文章浏览阅读521次。系统项目报表导出 导出任务队列表 + 定时扫描 + 多线程_积木报表 多线程
ajax 如何从服务器上获取数据？_ajax 获取http数据-程序员宅基地
文章浏览阅读1.1k次，点赞9次，收藏9次。使用AJAX技术的好处之一是它能够提供更好的用户体验，因为它允许在不重新加载整个页面的情况下更新网页的某一部分。另外，AJAX还使得开发人员能够创建更复杂、更动态的Web应用程序，因为它们可以在后台与服务器进行通信，而不需要打断用户的浏览体验。在Web开发中，AJAX（Asynchronous JavaScript and XML）是一种常用的技术，用于在不重新加载整个页面的情况下，从服务器获取数据并更新网页的某一部分。使用AJAX，你可以创建异步请求，从而提供更快的响应和更好的用户体验。_ajax 获取http数据
Linux图形终端与字符终端-程序员宅基地
文章浏览阅读2.8k次。登录退出、修改密码、关机重启_字符终端
随便推点
Python与Arduino绘制超声波雷达扫描_超声波扫描建模 python库-程序员宅基地
文章浏览阅读3.8k次，点赞3次，收藏51次。前段时间看到一位发烧友制作的超声波雷达扫描神器，用到了Arduino和Processing，可惜啊，我不会Processing更看不懂人家的程序，咋办呢？嘿嘿，所以我就换了个思路解决，因为我会一点Python啊，那就动手吧！在做这个案例之前先要搞明白一个问题：怎么将Arduino通过超声波检测到的距离反馈到Python端？这个嘛，我首先想到了串行通信接口。没错！就是串口。只要Arduino将数据发送给COM口，然后Python能从COM口读取到这个数据就可以啦！我先写了一个测试程序试了一下，OK！搞定_超声波扫描建模 python库
凯撒加密方法介绍及实例说明-程序员宅基地
文章浏览阅读4.2k次。端—端加密指信息由发送端自动加密，并且由TCP/IP进行数据包封装，然后作为不可阅读和不可识别的数据穿过互联网，当这些信息到达目的地，将被自动重组、解密，而成为可读的数据。不可逆加密算法的特征是加密过程中不需要使用密钥，输入明文后由系统直接经过加密算法处理成密文，这种加密后的数据是无法被解密的，只有重新输入明文，并再次经过同样不可逆的加密算法处理，得到相同的加密密文并被系统重新识别后，才能真正解密。2．使用时，加密者查找明文字母表中需要加密的消息中的每一个字母所在位置，并且写下密文字母表中对应的字母。_凯撒加密
工控协议--cip--协议解析基本记录_cip协议embedded_service_error-程序员宅基地
文章浏览阅读5.7k次。CIP报文解析常用到的几个字段：普通类型服务类型:[0x00], CIP对象:[0x02 Message Router], ioi segments:[XX]PCCC（带cmd和func）服务类型:[0x00], CIP对象:[0x02 Message Router], cmd:[0x101], fnc:[0x101]..._cip协议embedded_service_error
如何在vs2019及以后版本(如vs2022)上添加 添加ActiveX控件中的MFC类_vs添加mfc库-程序员宅基地
文章浏览阅读2.4k次，点赞9次，收藏13次。有时候我们在MFC项目开发过程中，需要用到一些微软已经提供的功能，如VC++使用EXCEL功能，这时候我们就能直接通过VS2019到如EXCEL.EXE方式，生成对应的OLE头文件，然后直接使用功能，那么，我们上篇文章中介绍了vs2017及以前的版本如何来添加。但由于微软某些方面考虑，这种方式已被放弃。从上图中可以看出，这一功能，在从vs2017版本15.9开始，后续版本已经删除了此功能。那么我们如果仍需要此功能，我们如何在新版本中添加呢。_vs添加mfc库
frame_size (1536) was not respected for a non-last frame_frame_size (1024) was not respected for a non-last-程序员宅基地
文章浏览阅读785次。用ac3编码，执行编码函数时报错入如下：[ac3 @ 0x7fed7800f200] frame_size (1536) was not respected for anon-last frame (avcodec_encode_audio2)用ac3编码时每次送入编码器的音频采样数应该是1536个采样，不然就会报上述错误。这个数字并非刻意固定，而是跟ac3内部的编码算法原理相关。全网找不到，国内音视频之路还有很长的路，音视频人一起加油吧～......_frame_size (1024) was not respected for a non-last frame
Android移动应用开发入门_在安卓移动应用开发中要在活动类文件中声迷你一个复选框变量-程序员宅基地
文章浏览阅读230次，点赞2次，收藏2次。创建Android应用程序一个项目里面可以有很多模块，而每一个模块就对应了一个应用程序。项目结构介绍_在安卓移动应用开发中要在活动类文件中声迷你一个复选框变量