KMP介绍
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
文字来源：百度百科
具体实现
x指针：用来做主串索引，y指针：用来做模式串索引。
重点：x不回溯，只通过移动y来匹配。
原理
- 开始时x，y都指向各自的第0个位置，当两索引处字符相等，x，y向后移动。
- 当不相等时，y移动到next[y]元素对应的位置，x不变
- 若y移动到-1处，x，y都向后移动
- 当x遍历完成后，若匹配成功，x-y的值即为主串对应模式串开始的第一个字符的索引，若匹配失败，返回-1
next数组
匹配过模式串前缀的“最长可匹配前缀子串”和“最长可匹配后缀子串”的最长共有元素的长度。
- 例如:ABABC 的 next[y]=2
- next数组的第一个元素为-1
前缀和前缀组合、后缀和后缀组合
- 前缀：去掉字符串最后一个元素后剩下的字符串
- 后缀：去掉字符串第一个元素后剩下的字符串
例如：ABABD 前缀就是 ABAB 后缀就是 BABD
- 前缀组合：前缀中，带有第一个元素的连续字符串组合
- 后缀组合：后缀中，带有最后一个元素的连续字符串组合
例如：ABABD 前缀组合有’A’,‘AB’,‘ABA’,‘ABAB’；后缀组合有：‘D’,‘BD’,‘ABD’,BABD’；
Java代码
import java.util.Arrays; /** * ClassName: KmpTest * Description: * date: 2021/2/19 10:15 * * @author ZhuQiPeng * @since JDK 1.8 */ public class KmpTest { public static void main(String[] args) { String desStr = "BABABACABABCABAABD"; String subStr = "ABABCABAAB"; int[] next = getNext(subStr); System.out.println(Arrays.toString(next)); int index = kmp(desStr,subStr); System.out.println(index); } public static int[] getNext(String subStr){ int[] next = new int[subStr.length()]; next[0] = -1; int len = -1, y = 0; while (y < subStr.length() - 1){ if(len == -1 || subStr.charAt(len) == subStr.charAt(y)) { y++; len++; next[y] = len; }else{ len = next[len]; } } return next; } public static int kmp(String desStr, String subStr){ int x = 0,y = 0; int[] next = getNext(subStr); while (x < desStr.length() && y < subStr.length()){ if(y == -1 || subStr.charAt(y) == desStr.charAt(x)){ x++; y++; }else{ y = next[y]; } } if (y == subStr.length()){ return x-y; }else{ return -1; } } }
