2、KMP算法
2.1、解决的问题
KMP是一个解决模式串在文本串是否出现过，如果出现过，找出最早出现的位置的经典算法，用来解决暴力匹配算法的不足
2.2、算法思路
2.2.1、部分匹配表的生成
什么是前缀与后缀：
- 前缀：ABCD的前缀为[A, AB, ABC]
- 后缀：ABCD的后缀为[BCD, CD, D]
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”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”，长度为 2；
- ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD,D]，共有元素的长度为 0。
如下表：
2.2.2、匹配过程
问题：假设有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
步骤：
-
首先，用 str1的第一个字符和 str2的第一个字符去比较，不符合，关键词向后移动一位
-
重复第一步，还是不符合，再后移
-
一直重复，直到 Str1有一个字符与 Str2的第一个字符符合为止
-
接着比较字符串和搜索词的下一个字符，还是符合
-
遇到 Str1有一个字符与 Str2对应的字符不符合
-
这时候不能像暴力匹配一样移动到最前面的下一个字符，因为前面的字符都匹配过了，当空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB”，这时候不要把”搜索位置”移回最前面的位置，而是根据匹配表，决定移动到哪个位置，这样就节省了效率，匹配表按照2.2.1的方法，进行计算
-
已知空格与 D 不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符 B 对应的”部分 匹配值”为 2， 因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值，因为 6 - 2 等于 4， 所以将搜索词向后移动 4 位。
-
此时C与空格不匹配，已经匹配的是“AB”两个字符，对应的”部分匹配值”为 0。
所以，移动位数 = 2 - 0， 结果为 2， 于是将搜索词向后移 2 位
-
继续按照字符，一个一个匹配，A与空格不匹配，后移一位，此时开始匹配
-
逐位比较，C和D不匹配，此时前面匹配的依然是“ABCDAB”，按照前面第六步的方法，构建匹配表，可知要往后移动4位
-
逐位匹配，此时发现完全匹配，代表找到了。
2.3、代码实现
import java.util.Arrays;
/**
* home.php?mod=space&uid=686208 yishuai
* @description kmp算法通俗易懂版
* home.php?mod=space&uid=686237 2021/4/7 7:06 下午
*/
public class Kmp {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
// int[] next = getNext("ABCDABD");
// System.out.println(Arrays.toString(next));
int i = KmpSearch(str1, str2);
System.out.println("找到的位置是："+ i);
}
/**
* 传入一个字符串，返回字符匹配表
* home.php?mod=space&uid=952169 match 要生成匹配表的字符串
* home.php?mod=space&uid=155549 返回匹配表数组
*/
public static int[] getNext(String match){
int[] next = new int[match.length()];
//第一个字符没有前缀和后缀，所以必定是0
next[0] = 0;
//指向字符串的头部
int j = 0,count=0;
//从第二个元素，开始和第一个比较
for (int i = 1; i < match.length(); i++) {
if (match.charAt(j) != match.charAt(i)){
count = 0;
}
//第一个元素和第i个元素匹配，代表前缀和后缀开始匹配
if (match.charAt(j) == match.charAt(i)){
next[i] = ++count;
//这样子匹配第一个字符后，就会匹配第二个字符
j++;
}
}
System.out.println(Arrays.toString(next));
return next;
}
/**
* kmp算法字符匹配的部分
* @param str1 源字符串
* @param str2 要被匹配的字符串
*/
public static int KmpSearch(String str1,String str2){
//count匹配成功的次数
int maxNum,count = 0;
//字符匹配数组
int[] next;
//首先要进行暴力匹配，比对第一个字符是否相同
for (int i = 0; i < str1.length(); i++) {
//代表第一个元素匹配上了
if (str2.charAt(count) == str1.charAt(i)){
//此时是进行第下个元素的匹配
count++;
//如果全部匹配上了，代表找到了，就结束
if(count == str2.length()){
//i跟着count一直往后走，所以要减去count，才是开头的位置，因为下标从0开始，所以要+1
return i - count + 1;
}
}else {
if (count != 0){
//代表没匹配成功了，此时要把匹配成功的这一段截取下来，生成字符匹配表
String substring = str2.substring(0, count);
next = getNext(substring);
maxNum = next[0];
//得到最大的字符匹配
for (int j = 0; j < next.length; j++) {
if (next[j] > maxNum){
maxNum = next[j];
}
}
//移动位数 = 已匹配的字符数 - 对应的部分匹配值
//最后还要-1，是因为for循环的i要++
i += count - maxNum - 1;
//匹配次数清零
count = 0;
}
}
}
return -1;
}
}