KMP的小笔记

为了维持两天一更，笔者只能把很早之前写的东西拿出来了，这篇文章是当时给女朋友写的笔记，也不知道她现在还会不会，忒找个机会考考她。

题目

判断一个字符串是否包含另一个字符串，若包含则返回下标，若不包含则返回-1.

下面讲解题目，讲解之前先进行名词规定

原字符串还叫原串

要匹配的字符串我们叫做匹配串

n代表原串的长度

m代表匹配串的长度

先看暴力解法

要理解匹配字符串的匹配算法是一个双指针算法，一个代表原串的索引，一个代表匹配串的索引，当匹配串的索引走到了头，也就意味着匹配完成了.

暴力的做法：

class Solution { 
    / * @param haystack: 原串 * @param needle: 匹配串 * @return: 匹配串在原串的起始位置 */ public int strStr(String haystack, String needle) { 
    if (needle.equals("")) { 
    return 0; } //获取长度 int n = haystack.length(); int m = needle.length(); //i是代表原串的索引，j代表匹配串的索引 //我们遍历到n - m + 1，往后也就代表着长度都不够了，直接返回未找到就行了 for (int i = 0; i < n - m + 1; i++) { 
    //我们提前设置标志位为true boolean flag = true; //遍历匹配串 for (int j = 0; j < m; j++) { 
    //如果说匹配串和原串不等修改标识位，进行下一次匹配 if (haystack.charAt(i + j) != needle.charAt(j)) { 
    flag = false; break; } } //返回起始位置 if (flag == true) return i; } return -1; } } 

思考暴力慢在了哪呢

暴力，每次匹配不成功，都是让原串的索引往下走一个，匹配串的索引从零重新开始，假设一个例子

原串 jnjnljnjnz 长度 n = 10

匹配串 jnjnz 长度 m = 5

在索引为4的时候发现 ‘l’ 和 ‘z’不相等，走到这，其实只差一步就能成功，真的就必须从头重新开始吗？

怎么做才能不从头开始呢，这就是KMP做的地方

再看KMP做了什么

先抛结论，KMP提前对匹配串进行了预处理，求匹配串每个位置上的最大缀等，也就是初始化next数组，这就是对暴力的优化。

结论目前不需要懂。

试想，为啥就可以不每次从头开始呢，是不是字符串前缀和后缀相等的原因，试着自己推一推。

先看最大缀等是啥

看例子jnjnljnjnz和 jnjnz,原串和匹配串的0-3索引是完全匹配的，看匹配串的一些特征，匹配串的0-3是jnjn，看一下它的最大相等的前缀和后缀是啥（前缀就是说从头往后，后缀就是从一个位置到尾巴）。

讯享网

我们先看一个例子，zjmazjm这个串的最大相等的前缀和后缀是啥呢，前缀zjm索引从0-2，后缀zjm索引从4-6，前缀串zjm和后缀串zjm是相等的，所以最大缀等就是3。

所以说jnjn的最大缀等就是2（前缀jn和后缀jn相等长度是2），我们再看个例子jnjnj，他的最大缀等是啥呢，前缀jnj和后缀jnj相等所以说最大缀等是3

知道最大缀等是啥了，那么看看最大缀等怎么起的作用

回头看例子jnjnljnjnz和 jnjnz，我们先看看jnjnz这个串每个位置的最大缀等

索引0 j默认为0

索引0 - 1 jn 一看就不存在前缀和后缀相等所以还是0

索引0 - 2 jnj 看0 j 和2 j相等 所以最大缀等是1

索引0 - 3 jnjn 看0 - 1 jn 和2 - 3 jn相等 所以最大缀等是2

索引0 - 4 jnjnz 一看就不等，为0

那jnjnz对应的next数组就是{0, 0, 1, 2, 0}

看jnjnljnjnz和 jnjnz

走一遍流程 ，设p是原串的索引，q是匹配串的索引，q如果最后等于了匹配串的长度则匹配成功了，原串是haystack，匹配串是needle

1. p，q指针都开始走，发现在索引为4的时候匹配失败
2. 查找next，我们看不匹配的串的最大缀等，因为是jnjnz，在p = 4，q = 4时haystack[p] != needle[q]，匹配失败开始移动
3. 我们看怎么移动，每次移动都是匹配不成功的前一个的最大缀等，看next[q - 1] 也就是next[3] = 2, 所以下次我们比较 haystack[4] 和 needle[2]，这一定要理解，为啥要比较前一个最大缀等，笔者是这么理解的，这是一个递归的过程，当不匹配则寻找上一个next，又不匹配等于，不匹配 + 不匹配，这是两个相同的问题，所以，不管几次不匹配，其实处理都是一样的，继续往下找next，直到q为0，或者匹配 也就是 while（q != 0 && haystack[p] != needle[q]）q = next[q];
4. 若又不相等，再移动，此时前一个就是next[1]了，next[1]为0，若是0的话，说明已经都匹配不了了，此时p要加1了，匹配haystack[5]和 needle[0]了，然后一直成功直到q = 匹配串长度

注意：p往后走只有两种情况，一种是我匹配成功往下走++，一种是我真的匹配不了了（next = 0的时候）也要往下走

KMP的代码实现（背背背）

这是笔者认为的最好背的kmp模版了，要背的关键代码就是一个循环，此模板是AcWing的Y总的

讯享网class Solution { 
    public int strStr(String haystack, String needle) { 
    if (needle.equals("")) { 
    return 0; } //我们用的模版，数组下标都从1开始 //获取原串字符数组 int n = haystack.length(); char[] s = new char[n + 1]; for (int i = 1;i <= n; i++) { 
    s[i] = haystack.charAt(i - 1); } //获取匹配串字符数组 int m = needle.length(); char[] p = new char[m + 1]; for (int i = 1;i <= m; i++) { 
    p[i] = needle.charAt(i - 1); } //构建next数组，java里数组不赋值的话默认为0 int[] next = new int[m + 1]; //从next[2]开始对next进行赋值，next[1]没动直接为0，符合要求 //求next数组的过程和匹配过程很像，其实就是自己和自己做匹配(一定要理解)，不过是从索引2开始的 for(int i = 2, j = 0; i <= m; i++) { 
    //如果匹配失败，则看之前能匹配上的是哪。试想，移动到那，是不是可能能匹配，只到真的匹配不上也就是j = next[j] = 0的时候，或者说是匹配上了 p[i] = p[j + 1]的情况 while(j != 0 && p[i] != p[j + 1]) j = next[j]; //如果匹配成功则往下走一位 if(p[i] == p[j + 1]) j++; next[i] = j; } //匹配过程 for(int i = 1, j = 0; i <= n; i++) { 
    while(j != 0 && s[i] != p[j + 1]) j = next[j]; if(s[i] == p[j + 1]) j++; //走完了，匹配成功 if(j == m) return i - m; } return -1; } } 

如有些地方不理解，就看看这个图，这个图画的挺好的，一定要多看几遍

总结：next数组的作用就是移动匹配串，为了避免让匹配串从头开始匹配。我们求的是最大缀等为啥最后直接转换成下标了呢，其实就是一个对应关系，可以自己试着推导一次，最大缀等其实正好就是我们下一个要比较的索引下标，也就是说缀等 = 要开始匹配的索引下标。

✨$原创不易，还希望各位大佬支持一下$

👍 $点赞，你的认可是我创作的动力！$

⭐️ $收藏，你的青睐是我努力的方向！$

✏️ $评论，你的意见是我进步的财富！$