【个人笔记】KMP算法菜鸟理解【java实现】

算法解释目录

问题引入暴力寻找分析图解步骤引入KMP算法KMP算法步骤详解next数组的原理（个人理解）JAVA算法实现

问题引入

现有一个 主字符串 “ABCDABBDEG”，一个 子字符串 “ABB”。 求 子字符串在主字符串中第一次出现的位置

暴力寻找分析

将子字符串的第一个字符与主字符串的第一个字符串进行匹配 若适配，则继续匹配下一位 若失配，则将子字符串向右移动一位，也就是子字符串的第一位去匹配主字符串的第二位直到子字符串全部匹配成功

图解步骤

子字符串的第一位与主字符串的第一位进行匹配，成功直到子字符串的第三位（B）与主字符串的第三位（C）失配

开始冗余 原因： 子字符串中的第一位（A）与第二位（B）已经与主字符串匹配成功，且这两位不相等 如果只是右移一位，那么很明显会在第一次匹配就失配 即应该右移两位，而不是一位

将子字符串向右移动一位，继续匹配将子字符串的第一位（A）与主字符串的第二位（B）进行匹配，失配 继续将子字符串右移将子字符串的第一位（A）与主字符串的第三位（C）进行匹配，失配 继续将子字符串右移将子字符串的第一位（A）与主字符串的第四位（D）进行匹配，失配 继续将子字符串右移将子字符串的第一位（A）与主字符串的第五位（A）进行匹配，适配将子字符串的第一位（A）与主字符串的第六位（B）进行匹配，适配将子字符串的第一位（A）与主字符串的第七位（B）进行匹配，适配匹配成功，返回 当前位-子字符串长度+1 即7-3+1=5；也就是第五位是其第一次出现的位置

引入KMP算法

上述暴力寻找的冗余已经在第三步时说明，而KMP算法就是为了解决这个问题 其中的核心是 next数组 ，而好多小白包括我 都栽在了理解next数组上 一开始不明白next数组存的是什么 后来不明白next数组为什么要存这些东西 所以弄懂next数组，就明白了KMP算法！！！

next数组存的是什么？

其存放的是子字符串已经匹配的部分字符串的 最大前缀、后缀公共字符串 举栗子： 有一个字符串：“ABCDAB” 前缀就是：“A”、“AB”、“ABC”、“ABCD”、“ABCDA” 后缀就是：“B”、“AB”、“DAB”、“CDAB”、“BCDAB” 而最大公共字符串则是：“AB”

next数组举例

这个是为了方便做的，真实next数组存放的是： next[0]：字符串 “A” 的最大前缀后缀公共字符串长度，即0 next[1]：字符串 “AB” 的最大前缀后缀公共字符串长度，即0 next[2]：字符串 “ABC” 的最大前缀后缀公共字符串长度，即0 next[3]：字符串 “ABCD” 的最大前缀后缀公共字符串长度，即0 next[4]：字符串 “ABCDA” 的最大前缀后缀公共字符串 （“A”） 长度，即1 next[5]：字符串 “ABCDAB” 的最大前缀后缀公共字符串 （“AB”） 长度，即2 next[6]：字符串 “ABCDABD” 的最大前缀后缀公共字符串长度，即0

KMP算法步骤详解

主字符串：ABCDABCAB 子字符串：ABCAB

next数组 {0,0,0,0,1,2}

next[0]：代表没有匹配字符，值为0

next[1]：字符串“A”

前缀：无后缀：无公共字符串：无最长公共长度：0

next[2]：字符串“AB”

前缀：“A”后缀：“B”公共字符串：无最长公共长度：0

next[3]：字符串“ABC”

前缀：“A”、“AB”后缀：“C”、“BC”公共字符串：无最长公共长度：0

next[4]：字符串“ABCA”

前缀：“A”、“AB”、“ABC”后缀：“A”、“CA”、“BCA”公共字符串：“A”最长公共长度：1

next[5]：字符串“ABCAB”

前缀：“A”、“AB”、“ABC”、“ABCA”后缀：“B”、“AB”、“CAB”、“BCAB”公共字符串：“AB”最长公共长度：2

开始匹配 以下描述，将子字符串称为S[ ]，将主字符串称为T[ ]

将S[0]和T[0]对齐，依次进行匹配当匹配到S[3]时，适配已经匹配的字符串为：“ABC”，查询next数组，可知部分匹配值为0将S[ ]向右移动：已经匹配的位数 - 部分匹配值 即 3 - 0 = 3 位S[0]与T[3]失配，已匹配的字符串为空，则向右移动一位匹配成功

next数组的原理（个人理解）

拿上个题的第二步来说： ☆ 已经匹配的字符串：“ABC” next数组求的是已经匹配的字符串的前后缀最大公共部分，而“ABC”没有公共部分，所以要移动3位

☆ 假设已经匹配的字符串是：“ABA” 如果不用程序，我们知道，应该将子字符串移动到T[2]处，因为T[2]等于A，即等于S[0] 那么next数组可以求出已匹配字符串“ABA”的最大前后缀公共部分“A”的长度1 也就是移动3-1=2位 刚好就是我们想要移动的地方

☆ 当已经匹配的字符串没有前后缀公共部分，那么就代表可以全部跳过

☆ 当已经匹配的字符串有前后缀公共部分，则跳到下一个匹配的地方

JAVA算法实现

public class KMP{ public static void main(String[] args){ //设置两个字符串，str1为主字符串，str2为子字符串 String str1="BBCABCDAB ABCDABCDABDE"; String str2="ABCDABD"; //调用kmpNext，生成next数组 int[] next=kmpNext(str2); //调用kmpSearch，得到结果 int index=kmpSearch(str1,str2,next); System.out.println("index=" + index); } //kmp算法 public static int kmpSearch(String str1,String str2,int[] next) { //遍历主字符串，抽象理解的话，for循环是让主字符串不动，只是子字符串动 //而j则是当前匹配的指针 //如果已匹配字符串的部分匹配值为0，i不变，而j置零 //也就是相当于将子字符串向右移动已匹配字符串的长度位 for(int i=0,j=0;i<str1.length();i++) { //若失配，且有已经匹配的字符串，那么查找next数组，找到部分匹配值 while(j>0 && str1.charAt(i) != str2.charAt(j)) { j=next[j-1]; } //记录已经匹配字符串长度j if(str1.charAt(i) == str2.charAt(j)) { j++; } //若已经匹配字符的长度j等于子字符串的长度，代表全部匹配，也就是已经找到，返回位置。 if(j == str2.length()) { return i-j+1; } } return -1; } //next数组 public static int[] kmpNext(String dest) { //创建next数组 int[] next = new int[dest.length()]; next[0] = 0; //如果字符串长度为1，部分匹配值为0 //让字符串中的j位一直和i位比较 //如果相等，就j+1（“ABA”） //如果不相等，且之前相等（j>0),（“AAAD"），j则会向前，直至找到D，也就是找到前缀包括D的那项。 for(int i = 1,j = 0;i < dest.length();i++) { while(j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j-1]; } if(dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; } }

代码是拷贝的尚硅谷老师讲课内容里的，加上了自己的注释。