持续创造，加速生长！这是我参加「日新方案 10 月更文挑战」的第30天，点击查看活动概况

1、写在前面

大家好，我是翼同学。今日文章的内容是：

KMP算法

在学完算法与数据结构中串的课程后，对KMP算法有种似懂非懂的感觉。今日就系统的再对KMP算法进行梳理和归纳，

2、串的形式匹配

在数据结构中，串归于线性结构，是一种数据元素为字符的特别线性表。而串的特别性在于，操作的方针不再是单个元素，而是一组元素。比方在线性表中查找某个元素，比方在线性表中，咱们一般会查找、插入或删去某个元素，而在串中，咱们还能在某个方位查找、插入或删去某段子串。即以“一段子串”为操作方针。

举个比如，假定咱们现在有一段主串S（方针串）和子串P（形式串），此刻的需求是在主串S中找到一个与子串P持平的子串，假如找到了就回来子串P在主串S中榜首次呈现的方位。

像这种子串的定位操作，一般被咱们称为形式匹配（或模型匹配）。

3、BF算法

3.1、算法思路

关于子串的形式匹配，假如采用朴素的形式匹配（Brute-Force算法，简称BF算法）思路，则算法思维如下：

假定现在方针串S匹配到i方位，形式串P匹配到j方位
假如此刻S[i] == P[j]（字符匹配成功），则持续匹配下一个字符，即i++, j++
假如此刻S[i]! = P[j]（字符匹配失利），则使i回溯，j则重置为0，即i = i - (j - 1)，j = 0
不断进行朴素的形式匹配
假如最终匹配成功，则回来形式串的榜首个字符在方针串中榜首次呈现的方位
假如匹配失利，则回来-1。

3.2、参阅代码

依据朴素的形式匹配算法思路，咱们很简单写出代码。

参阅代码如下：

// 设定s是方针串，p是形式串
int bfFind(char* s, char* p) {  
    int sLen = strlen(s);   // 方针串的长度
    int pLen = strlen(p);   // 形式串的长度
    int i = 0;              // 指向方针串的下标
    int j = 0;              // 指向形式串的下标
    while (i < sLen && j < pLen) {
        // 当字符持平时，指针后移，匹配下一个字符 
        if (s[i] == p[j]) {  
            i++;  
            j++;  
        }
        // 假如字符匹配失利，则指针i回溯，j则重置为0
        else {    
            i = i - j + 1;  
            j = 0;  
        }
    }
    // 假如匹配成功，则回来形式串 p 的榜首个字符在方针串中呈现的方位  
    if (j == pLen) {
        return i - j;
    }
    // 假如匹配失利，则回来-1 
    else{
        return -1;
    }
}

3.3、暗示图

首要咱们设定：

方针串为：PFABCDR GABCDE
形式串为：ABCDE
最终经过形式匹配后，结果回来9
也便是说，形式串中的榜首个字符（A）在方针串中呈现的方位为s[9]。

下面是朴素的形式匹配进程暗示：

(1) 形式串不断往后移动

能够看到：

s[0]为p
p[0]为A
此刻s[0] != p[0]，很明显字符不匹配，因而：
令i回溯：i = i-(j-1)，即0-(0-1)，i变成了1
令j重置为零：即j = 0
这种作用其实便是将形式串s要往后移动一位

能够看到，将形式串往右边移动后：

s[1]为F
p[0]为A
此刻s[1] != p[0]，字符不匹配，因而：
令i回溯：i = i-(j-1)，即1-(0-1)，此刻i变成了2
令j重置为零：即j = 0
形式串s不断往后移动。

(2) 暂时匹配成功

能够看到：

s[2]为A
p[0]为A
此刻s[2] == p[0]，对应字符成功匹配，因而：
两指针一起后移，即i++; j++;
此刻i=3, j=1，持续往后匹配。

能够看到：

s[3]为B
p[1]为B
此刻s[3] == p[1]，对应字符成功匹配，因而：
两指针一起后移，即i++; j++;
此刻i=4, j=2，持续往后匹配，不断重复这个进程…

(3) 再次匹配失利

能够看到：

s[6]为R
p[4]为E
此刻s[6] != p[4]，对应字符再次不匹配，因而：
令i回溯：i = i-(j-1)，即6-(4-1)，i变成了3
令j重置为零：即j = 0
此刻形式串s又再次往后移动一位。

(4) 最终匹配成功

能够看到，到最终：

s[13]为E
p[4]为E
此刻s[14] != p[4]，对应字符匹配，因而：
两指针一起后移，即i++; j++;
此刻i=14, j=5
因为不满意i < sLen && j < pLen，所以退出循环
最终return i - j;，也便是回来10（方针串中A的下标就为10）

(5) 小结

到这儿，咱们能够发现，关于朴素的形式匹配算法来说，咱们很简单了解，代码简单易懂。但缺陷也很大，便是i需求屡次回溯。假如关于数据量较大的文件，朴素的形式匹配其实是功率很低的。为了进步形式匹配的算法功率，咱们需求削减字符匹配的次数以及回溯的次数。

比方在前文给出的匹配进程中：

尽管形式串和方针串现已成功匹配了四个字符ABCD
s[6] != p[4]，即'R' != 'E'
所以方针串就回溯到s[3]，形式串则被重置为p[0]
也便是将形式串向后移动一位，然后持续匹配（让s[3]和p[0]进行字符匹配）

为了进步形式匹配的算法功率，下面咱们来学习KMP算法

4、KMP算法

4.1、简介

KMP算法的简介如下：

KMP算法是一种改善的字符串匹配算法

由D.E.Knuth，J.H.Morris和V.R.Pratt提出的

因而人们称它为Knuth-Morris-Pratt算法（简称KMP算法）

KMP算法的核心是使用匹配失利后的信息

尽量削减形式串与主串的匹配次数以达到快速匹配的意图

具体完结便是经过一个next()函数完结

next()函数自身包含了形式串的局部匹配信息

KMP算法的时刻复杂度 $O (m + n)$

关于KMP算法来说，主要特点便是主串（方针串）不必回溯，主串指针i一直往后面移动，只有子串（形式串）的指针j在回溯。这就大大削减了形式匹配算法的比较次数以及回溯次数。KMP算法能够在 $O (m + n)$ 的时刻复杂度量级上完结串的形式匹配。

4.2、引进

回顾前文的匹配进程：

这趟匹配中，在i=6, j=4下标处，对应字符不匹配，
在朴素的形式匹配下，i, j都将回溯
也便是又从i=3, j=0下标处从头开端进行匹配。

如下所示：

但实际上能够发现，i=3和j=0、i=4和j=0、i=5和j=0这三趟字符匹配，彻底没必要进行，也便是说能够省掉掉这几回字符匹配的进程，将子串向右滑动3个字符，持续从i=6, j=0下标处开端匹配即可。

如下所示：

也便是说，在KMP算法下，当方针串下标为i的字符与方针串中下标为j的字符不匹配时，方针串指针i不回溯，形式串指针j回溯到一个适宜的方位，从头进行比较（形式串相关于方针串，是向右移动的）。

明白了这个思路后，咱们再来看看，形式串指针j应该滑动到哪个适宜的方位才适宜呢？

4.3、KMP算法思维

KMP算法采用以空间换时刻的方式，请求一个与子串长度持平的整型数组next，令next[j] = k，则next[j]表明当子串中p[j]与主串中s[i]匹配失利时，在子串中需求从头和主串中s[i]进行匹配的字符的方位k。也便是说，当形式匹配时呈现失配时，主串下标i不变，使用next数组求出子串下标为j的方位失配时需求滑动到的新方位k。

这便是KMP算法的基本思维。

咱们先不管next数组是怎么计算得到的，先看看KMP算法的具体流程。

如下所示：

设定主串匹配到s[i]处，子串匹配到p[j]处
假如当时j = -1或者s[i] == p[j]，则代表当时字符匹配成功，此刻让指针变量都往后移动一位，持续匹配下一个字符
假如j != -1而且s[i] != p[j]，则代表当时字符匹配失利，此刻令i不变，而将j赋值为next[j]，其实便是子串相关于主串向后移动了j - next[j]位。

因而在KMP算法中，当形式串的某个字符跟方针串中的某个字符不匹配时，next数组会告知形式串下一步匹配时应当在哪个方位，而不是傻乎乎的将形式串往后移一位。

4.4、KMP算法代码

依据KMP算法思路，咱们很简单写出代码。

参阅代码如下：

// 设定 s 是方针串， p 是形式串
int KMPFind(char* s, char* p) {  
    int sLen = strlen(s);   // 方针串的长度
    int pLen = strlen(p);   // 形式串的长度
    int i = 0;              // 指向方针串的下标
    int j = 0;              // 指向形式串的下标
    // 界说next数组
    int *next = new int [pLen];
    getNext(next, p);
    while (i < sLen && j < pLen) {
        // 当字符持平时，指针后移，匹配下一个字符 
        if (j == -1 || s[i] == p[j]) {  
            i++;  
            j++;  
        }
        // 假如 j!=-1 而且s[i] != p[j]，则表明字符匹配失利
        // 此刻指针 i 不回溯，j 则重置为next[j]
        else {    
            j = next[j];
        }
    }
    // 假如匹配成功，则回来形式串 p 的榜首个字符在方针串中呈现的方位  
    if (j == pLen) {
        return i - j;
    }
    // 假如匹配失利，则回来-1 
    else{
        return -1;
    }
}

4.5、next 数组

(1) 求解 k 的值

现在咱们假定：

主串 $S$ = “ $S_0$ $S_1$ $S_2$ … $S_{n-1}$ “
子串 $P$ = “ $P_0$ $P_1$ $P_2$ … $P_{m-1}$ “

则在KMP算法中，当 $S_i$ 和 $P_j$ 匹配失利时，主串不回溯，而子串中的第 $k$ 个字符 $P_k$ 将与主串 $S_i$ 持续进行匹配。

暗示图如下：

主串：

子串：

假如子串中” $P_0$ $P_1$ … $P_{j-1}$ “现已完结匹配
但此刻 $P_j$ 不等于 $S_i$ 时，匹配失利后
此刻主串指针i不必动
子串也不必重置为0，不必从头开端匹配
而是将子串回溯到下标为k的方位与主串持续进行匹配：
暗示图如下：

也便是说，当产生字符匹配失利时，仅需将子串向右滑动至子串中下标为k的字符，与主串中下标为i的字符对齐，持续进行匹配即可。这是因为子串前面的k个字符必定与主串中下标为i的字符前长度为k的子串持平。

到这儿，你就会发现，KMP算法的关键问题现已变成了如何求解 k 的值。

(2) 最长持平前后缀

首要记录一下什么是前后缀子串：

前缀：指的是不包含最终一个字符的一切以榜首个字符开头的接连子串
后缀：指的是不包含榜首个字符的一切以最终一个字符结尾的接连子串

正确了解前后缀子串的含义，关于后续了解next数组来说有很大的协助。

前文简述了k值的重要性，或许看起来不太直观。现在咱们来看一道例题:

主串 $S$ 为：”abc123abc123abcd”
子串 $P$ 为：”123abcd”
在串的形式匹配中，会呈现这样的情况，如下图：

能够看到，s[9] != p[9]，此刻假如是朴素的形式匹配算法，则i会回溯到1，j则会重置为0。但是在KMP算法中，主串指针i不动，子串指针j会回溯到k的方位（实际上k的值便是next[j]），如下图所示：

因而，为了确认k的值：

咱们会在子串P中寻觅最长相同的
前缀子串 “ $P_0$ $P_1$ … $P_{k-1}$ “
以及后缀子串 “ $P_{j-k}$ $P_{j-k+1}$ … $P_{j-1}$ “。
假如找到了最长的相同的前后缀子串，则k的值就能够确认了。

(3) 什么是next数组？

无论是k值，还是最长持平前后缀子串，都是为了解next数组而服务。

那么next数组究竟是什么？

其实，next数组便是用来让形式串指针j进行合理地回溯，其记录了形式串与方针串不匹配时，形式串应该从哪里开端从头匹配。

而前文说到的k值，便是next[j]：

在KMP算法中，咱们请求一个整型数组next
而且令next[j] = k
则next[j]表明当子串中 $P_j$ 和主串中 $S_i$ 失配时，
在子串中需求从头和主串中的 $S_i$ 进行匹配的字符下标为k。

也便是说，next数组要求的便是最长相同前后缀的长度。

因而，每个字符对应的next数组值，其实便是该字符之前的子串中包含最大长度的相同前后缀子串。注意，了解这一句话很重要。

(4) 如何获取next数组？

下面给出获取next数组的参阅代码：

void getNext(char* p, int next[]) {
    int pLen = strlen(p);   // 取到子串的长度 pLen 
    next[0] = -1;           // next[0]初始化为-1, 表明子串现已滑动到头 
    int k = -1;             // p[k]表明前缀子串
    int j = 0;              // p[j]表明后缀子串
    // 遍历子串
    while (j < pLen - 1) { 
        if (k == -1 || p[j] == p[k]) {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else {  
            k = next[k];  
        }  
    }  
}

备注：

发问：为什么next[0]要初始化为-1 ？
答复：这是为了表明当子串指针j指向下标为0的元素在匹配失利后进行下一轮匹配时，子串指针j依然能够指向下标为0的元素。

(5) 比如

现在给出几张next数组求解的暗示图，协助了解next数组的求解进程。

假定现在有一段形式串 P = abc123abcd"，使命是求出其next数组：

# 初始化

设k = -1，j = 0，而且next[0] = -1

# 第1轮循环

初始化作业完结后，就开端榜首轮循环：
此刻k = -1刚好满意if句子的判别条件
则直接履行if句子块，j和k先自增，即k = 0, j = 1
接着便是next数组元素的赋值：next[j] = k
因而next[1]就等于0
进程如下：

# 第2轮循环

进入第二轮循环后，因为k = 0而且p[j] = "b"，p[k] = "a"，二者并不持平
因而不满意if判别句子，此刻履行else句子块：
k = next[k]，即k = next[0]。因而k就又变成了-1
进程如下：

# 第3轮循环

进入第三轮循环后，因为k = -1，满意if句子的判别条件
因而履行if句子块，j和k先自增，即j = 2，k = 0
接着便是next数组元素的赋值：next[j] = k，即next[2] = 0
进程如下：

# 第4轮循环

进入第四轮循环后
因为j = 2, k = 0而且p[j] = "c"，p[k] = "a"，二者并不持平
因而不满意if判别句子，此刻履行else句子块：
k = next[k]，即k = next[0]。因而k就又变成了-1
进程如下：

# 第5轮循环

进入第五轮循环后，因为k = -1，满意if句子的判别条件
因而履行if句子块，j和k先自增，即j = 3，k = 0
接着便是next数组元素的赋值：next[j] = k，即next[3] = 0
进程如下：

# 第6轮循环

进入第六轮循环后
因为j = 3, k = 0而且p[j] = "1"，p[k] = "a"，二者并不持平
因而不满意if判别句子，此刻履行else句子块：
k = next[k]，即k = next[0]。因而k就又变成了-1
进程如下：

# 第7轮循环

进入第七轮循环后，因为k = -1，满意if句子的判别条件
因而履行if句子块，j和k先自增，即j = 4，k = 0
接着便是next数组元素的赋值：next[j] = k，即next[4] = 0
进程如下：

# 第8轮循环

进入第八轮循环后
因为j = 4, k = 0而且p[j] = "2"，p[k] = "a"，二者并不持平
因而不满意if判别句子，此刻履行else句子块：
k = next[k]，即k = next[0]。因而k就又变成了-1
进程如下：

# 第9轮循环

进入第九轮循环后，因为k = -1，满意if句子的判别条件
因而履行if句子块，j和k先自增，即j = 5，k = 0
接着便是next数组元素的赋值：next[j] = k，即next[5] = 0
进程如下：

# 第10轮循环

进入第十轮循环后
因为j = 5, k = 0而且p[j] = "3"，p[k] = "a"，二者并不持平
因而不满意if判别句子，此刻履行else句子块：
k = next[k]，即k = next[0]。因而k就又变成了-1
进程如下：

# 第11轮循环

进入第十一轮循环后，因为k = -1，满意if句子的判别条件
因而履行if句子块，j和k先自增，即j = 6，k = 0
接着便是next数组元素的赋值：next[j] = k，即next[6] = 0
进程如下：

# 第12轮循环

进入第十二轮循环后
因为j = 6, k = 0
而且此刻p[j] = "a"，p[k] = "a"：二者持平！字符匹配成功！
因而满意if判别句子，此刻履行if句子块：
j和k先自增，即j = 7，k = 1
接着便是next数组元素的赋值：next[j] = k，即next[7] = 1
进程如下：

# 第13轮循环

进入第十三轮循环后
因为j = 7, k = 1
而且此刻p[j] = "b"，p[k] = "b"：二者持平！字符匹配成功！
因而满意if判别句子，此刻履行if句子块：
j和k先自增，即j = 8，k = 2
接着便是next数组元素的赋值：next[j] = k，即next[8] = 2
进程如下：

# 第14轮循环

进入第十四轮循环后
因为j = 8, k = 2
而且此刻p[j] = "c"，p[k] = "c"：二者持平！字符匹配成功！
因而满意if判别句子，此刻履行if句子块：
j和k先自增，即j = 9，k = 3
接着便是next数组元素的赋值：next[j] = k，即next[9] = 3
进程如下：

# 退出循环

至此，因为j = 9 不满意循环条件while(j < pLen-1)，因而退出循环。

所以最终，咱们也得到了形式串P的next数组，如下所示：

5、总结

总结一下，关于串的形式匹配中:

在BF算法（朴素的形式匹配，简称暴力检索）中，当主串和子串产生失配时，主串和子串的指针都需求回溯，然后再进行匹配。所以该算法的时刻复杂度较高，达到 $O (n m)$ ，空间复杂度为 $O (1)$ 。
在KMP算法中，咱们设计了一个next数组，用于达到主串不回溯，让子串指针有规律回溯的意图，这样就削减了回溯和匹配的次数，大大提升了形式匹配的功率。简单来说，KMP的算法思维是当呈现对应字符不匹配时，能够先记录一部分之前现已匹配的文本内容，使用这些信息避免从头再去做匹配。但这是建立在牺牲了存储空间的基础上进行的。KMP算法的时刻复杂度为 $O (n + m)$ ，空间复杂度为 $O (n)$

6、刷题稳固

6.1、找出字符串中榜首个匹配项的下标

学完KMP算法后，能够测验刷这道题：找出字符串中榜首个匹配项的下标，咱们能够用KMP算法去解这道题。

链接：28. 找出字符串中榜首个匹配项的下标 – 力扣（LeetCode）

(1) 描述

(2) 举例

(3) 提示

6.2、使用KMP算法解题

参阅代码（C++版）如下：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int sLen = haystack.length(); // 获取主串的长度
        int pLen = needle.length();   // 获取子串的长度
        // 假如形式串的长度为0，则回来0
        if(pLen == 0) return 0;
        int next[pLen];         // 界说next数组，用形式串的长度去赋值数组的巨细
        getNext(next, needle);  // 为next数组的数据元素赋值
        int i = 0;   // 主串指针
        int j = 0;   // 子串指针
        // 循环遍历
        while(i < sLen && j < pLen) {
            // 当字符持平时，指针后移，匹配下一个字符 
            if (j == -1 || haystack[i] == needle[j]) {  
                i++;  
                j++;  
            }
            // 假如 j!=-1 而且s[i] != p[j]，则表明字符匹配失利
            // 此刻指针 i 不回溯，j 则重置为 next[j]
            else {    
                j = next[j];
            }
        }
        // 假如匹配成功，则回来形式串 p 的榜首个字符在方针串中呈现的方位  
        if (j == pLen) {
            return i - j;
        }
        // 假如匹配失利，则回来-1 
        else{
            return -1;
        }
    }
    // 自界说函数，用于获取 next 数组
    void getNext(int* next, string& p) {
        int pLen = p.length();
        int k = -1;
        int j = 0;
        next[0] = -1;
        while(j < pLen - 1) {
            if(k == -1 || p[j] == p[k]) {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
    }
};

7、写在最终

好了，关于串的形式匹配，就先记录到这儿，假如文章有出错的当地，请大佬们指出。今日文章的内容就写到这儿，感谢观看。

【串】：一看就懂的KMP算法（六千字总结，多图预警）

1、写在前面

2、串的形式匹配

3、BF算法

3.1、算法思路

3.2、参阅代码

3.3、暗示图

(1) 形式串不断往后移动

(2) 暂时匹配成功

(3) 再次匹配失利

(4) 最终匹配成功

(5) 小结

4、KMP算法

4.1、简介

4.2、引进

4.3、KMP算法思维

4.4、KMP算法代码

4.5、next 数组

(1) 求解 k 的值

(2) 最长持平前后缀

(3) 什么是next数组？

(4) 如何获取next数组？

(5) 比如

# 初始化

# 第1轮循环

# 第2轮循环

# 第3轮循环

# 第4轮循环

# 第5轮循环

# 第6轮循环

# 第7轮循环

# 第8轮循环

# 第9轮循环

# 第10轮循环

# 第11轮循环

# 第12轮循环

# 第13轮循环

# 第14轮循环

# 退出循环

5、总结

6、刷题稳固

6.1、找出字符串中榜首个匹配项的下标

(1) 描述

(2) 举例

(3) 提示

6.2、使用KMP算法解题

7、写在最终

相关文章

SpringBoot集成支付宝支付 – 少走弯路就看这篇

优雅的实现字典翻译

Android 插件化（插件内部跳转）

读《刻意练习》小记（中）

作者信息

推广