KMP算法
本帖最后由 逸帅 于 2021-4-21 19:18 编辑## 2、KMP算法
### 2.1、解决的问题
> KMP是一个**解决模式串在文本串是否出现过**，如果出现过，找出最早出现的位置的经典算法，用来解决暴力匹配算法的不足
### 2.2、算法思路
#### 2.2.1、部分匹配表的生成
什么是**前缀与后缀**：
- 前缀：ABCD的前缀为
- 后缀：ABCD的后缀为
部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，
- ”A”的前缀和后缀都为空集，共有元素的长度为 0；
- ”AB”的前缀为，后缀为，共有元素的长度为 0；
- ”ABC”的前缀为，后缀为，共有元素的长度 0；
- ”ABCD”的前缀为，后缀为，共有元素的长度为 0；
- ”ABCDA”的前缀为[**A**, AB, ABC, ABCD]，后缀为，共有元素为***”A”***，**长度为 1**；
- ”ABCDAB”的前缀为，后缀为，共有元素为***”AB”***，**长度为 2**；
- ”ABCDABD”的前缀为，后缀为，共有元素的长度为 0。
如下表：
#### 2.2.2、匹配过程
> 问题：假设有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
步骤：
1. 首先，用 str1的第一个字符和 str2的**第一个字符去比较，不符合，关键词向后移动一位**
2.重复第一步，还是不符合，再后移
3.一直重复，直到 Str1有一个字符与 Str2的**第一个字符符合为止**
4.接着比较字符串和搜索词的下一个字符，还是符合
5.遇到 Str1有一个字符与 Str2对应的字符**不符合**
6.这时候不能像暴力匹配一样移动到最前面的下一个字符，因为前面的字符都匹配过了，当空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB”，这时候不要把”搜索位置”移回最前面的位置，而是根据匹配表，决定移动到哪个位置，这样就节省了效率，匹配表按照2.2.1的方法，进行计算
7.已知空格与 D 不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符 B 对应的”部分 匹配值”为 2， 因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值，因为 6 - 2 等于 4， 所以将搜索词向后移动 4 位。
8.此时C与空格不匹配，已经匹配的是“AB”两个字符，对应的”部分匹配值”为 0。
所以，移动位数 = 2 - 0， 结果为 2， 于是将搜索词向后移 2 位
9.继续按照字符，一个一个匹配，A与空格不匹配，后移一位，此时开始匹配
10.逐位比较，C和D不匹配，此时前面匹配的依然是“ABCDAB”，按照前面第六步的方法，构建匹配表，可知要往后移动4位
11.逐位匹配，此时发现完全匹配，代表找到了。
### 2.3、代码实现
```java
package com.yishuai.Algorithm;
import java.util.Arrays;
/**
* @author yishuai
* @description kmp算法通俗易懂版
* @date 2021/4/21 1:06 下午
*/
public class KmpDemo {
public static void main(String[] args) {
String str1 = "ABCABCD ABCDABCABCABCDE";
String str2 = "ABCABCA";//[-1,0,0,0,1,2,3,0]
// String str2 = "abcabd";
// String str2 = "abcabcba";
// 这个是区分大小写的，因为比较用的==号，比较的是ASCII值，
// 如果要不区分大小写，需要在比较的时候，用equalsIgnoreCaseA
// String str2 = "abc";
//先构建字符匹配表，后面的匹配过程，只需要查表即可
int[] next = getNext(str2);
System.out.println("字符匹配表是：" + Arrays.toString(next));
int i = KmpSearch(str1, str2, next);
System.out.println("找到的位置是：" + i);
}
/**
* 传入一个字符串，返回字符匹配表
*
* @param str2 要生成匹配表的字符串
* @return 返回匹配表数组
*/
public static int[] getNext(String str2) {
int[] next = new int;
// 第一位，匹配值为0
next = -1;
next = 0;
//j表示从第一位开始，i表示要对比的位置
for (int i = 2, j = 0; i < next.length; i++) {
while (str2.charAt(i - 1) != str2.charAt(j) && j != 0) {
/**
* 这里是关键点
* 推荐视频:https://www.bilibili.com/video/BV16X4y137qw
* 跳到14：18看图解就懂了，我看了六遍
*/
j = next;
}
if (str2.charAt(i - 1) == str2.charAt(j)) {
j++;
}
next = j;
}
return next;
}
/**
* kmp算法字符匹配的部分
*
* @param str1 源字符串
* @param str2 要被匹配的字符串
*/
public static int KmpSearch(String str1, String str2, int[] next) {
// 查找匹配位置
for (int i = 0, j = 0; i < str1.length(); i++) {
while (str1.charAt(i) != str2.charAt(j) && j > 0){
j = next;
}
if(str1.charAt(i) == str2.charAt(j)){
/**
* 当最后一位数相等的时候，就不要再让他做++操作了
* 此时刚刚好i往前走了j步
*/
if (j == str2.length() - 1){
return i - j + 1;
}
j++;
}
}
return -1;
}
}
``` niebaohua 发表于 2021-4-20 17:21
获取 部分匹配值好像不太对
例如：字符串 `aabaaac`
这一段的kmp匹配表，我好像只做了第一次的判断，后面的判断没有做，所以返回的值会存在错误，我昨天发现的这个问题，在准备改{:301_978:} 我弄个kmp算法讲解的视频，上传到动画区去{:301_978:} 感谢，昨天刚学习到kmp 好好学习多挣钱 发表于 2021-4-7 20:40
感谢，昨天刚学习到kmp
怎么样，学懂了没，主要是代码，写出来没{:301_978:} 感谢，分享 有学习到 高手，学习了。
这个就是造轮子吗？ 我大一的课程设计题目就是关于kmp算法{:301_997:} 厉害了楼主，最近刚好在学kmp算法，学习了~ 清晰明了，之前都没怎么学过算法。 有点意思哦，看一遍就理解了，又学到了非常感谢。