KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
文字来源：百度百科

目录

具体实现：

原理：

next数组：

总结

具体实现：

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’；

import java.util.Arrays;

/**
 * @author Sun
 * @version 2021.2
 * @date 2022/5/28 17:42
 */
public class KmpTest {
    public static void main1(String[] args) {
        String parentStr = "bacabc";
        String childStr = "  abc";
    
        int[] next = getNext(childStr);
        System.out.println(Arrays.toString(next));

        int index = kmp(parentStr,childStr);
        System.out.println(index);

    }

    private static int kmp(String parentStr, String childStr) {
        int x = 0,y = 0;
        int[] next = getNext(childStr);

        while (x < parentStr.length() && y < childStr.length()){
            if (y == -1 || childStr.charAt(y) == parentStr.charAt(x)){
                x++;
                y++;
            }else {
                y = next[y];
            }
        }
        if (y == childStr.length()){
            return x-y;
        }else {
            return -1;
        }
    }

    private static int[] getNext(String childStr) {
        int[] next = new int[childStr.length()];
        next[0] = -1;
        int len = -1,y=0;

        while(y < childStr.length() - 1){
            if (len == -1 || childStr.charAt(len) == childStr.charAt(y)) {
                y++;
                len++;
                next[y]=len;
            }else {
                len = next[len];
            }
        }
        return next;
    }
}

总结

注意：
1、KMP算法的核心就是避免所有不必要的回溯，并用next[]数组记录应该回溯到的位置，用指定回溯的位置代替遍历式地回溯，以此提高效率。可以看出，next[]的生成是KMP算法的核心，应重点理解。
2、每个子串都对应一个唯一的next[]数组，与要匹配的主串无关，因为在KMP算法中，主串不回溯，只自增，next[]记录的是子串要回溯到的位置。
3、getNext()与KMP()的结构十分相似，但思想有很大不同，要注意区分：getNext()中只有一个字符串，进行的是前缀和后缀的比较；KMP()中有两个字符串，进行的是字符串和字符串的比较，比较后子串根据next[]进行回溯。
4、如果不理解，可以带入一个子串推导一遍，这样能更直观地理解其中的过程。
5、不难看出，KMP算法仅在子串自身重复度较高时更高效，若子串重复度不高，则与朴素算法差别不大。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/119573.html