Hello，大家好，本文将为你带来的是数据结构中有关==串的模式匹配问题==，主要讲解的是BF算法和KMP算法

@TOC

💪BF暴搜

🦏前言及代码罗列

有关字符串的匹配问题，是大家比较头疼的一块，首先我们来说一说使用BF【Brute-Force】暴搜来如何解决

• 代码千万条，暴力第一条，对于字符串，大家首先想到的肯定是利用暴力去完成，虽然显得会有些直接一些，但有时候直接并不是一种坏事，能AC但不超时不就好了
• 暴力的代码并不复杂，首先给出代码

int BF(SqString s, SqString t)
{
	int i = 0, j = 0;
	while (i < s.length && j < t.length)	//知道两个串扫描完成
	{
		if (s.data[i] == t.data[j]){		//比较两个串的字符数值
			i++;	
			j++;		//若是相等则一同向后继续查找
		}
		else {		//若是不同
			i = i - j + 1;		//目标串i回退
			j = 0;		//子串t从头开始匹配
		}
	}
	if (j == t.length)
		return i - t.length;
	else
		return -1;
}

🦏算法图示及讲解

• 首先给出两个串，一个是目标搜索串，一个是匹配子串。初始的时候都是位于各串的首部，从前往后开始搜索，然后通过一个while循环来控制搜索的范围。在搜索的过程中，若是两个字符相同，则继续向后查找，若是不同，则更新查找的位置。
• 当这个子串超出末端边界后，便跳出while循环，返回子串t在主串s中第一个字符出现的位置

然后我们通过算法图示一步步来走一下，就能很清楚明晰了

• 首先一开始，i指向主串s的首部，j指向子串t的首都，【a == a】，因此一起累加，进入下一个字符的匹配

• 接着又是【a == a】,所以继续向后查找:point_right:

• 然后就可以看到，【f != b】，因此这个进入另一分支的判断，然后更新i下标在主串中的位置，其实【i - j + 1】这个公式是计算出来的，就是让这个i每次后进一位，但是对于当前位置来说是要后退的
• 【i - j + 1】此时为1，所以来到了1的位置。然后j的话重新置为0，这个毋庸置疑，因为你要在后面继续查找这个子串的位置，所以必须要所有都匹配，因此j才要回退到子串的最初位置

• 此时可以看到，又不匹配了，所以继续重置两个指针的位置

• 继续重置

• 可以看出，此时都是匹配的，因此我们按下快进⏩
• 然后便可以看到，此时对最后一个位置进行匹配，是匹配的，所以i与j继续++

• 此时i与j均是超出了边界，这种比较特殊一些，一般都是子串位于主串的其他位置，然后子串超出边界，就意味着匹配成功，不过这种情况也是符合循环条件的

• 接着就来到了下面，我们需要获取此时子串在主串出现的位置，【i - t.length】便可以获取例子中此时i 是6，因此超出了边界，然后t.length的话是3，减一下的话就是3

if (j == t.length)
	return i - t.length;
else
	return -1;

• 从我上图标出的坐标来看，这个子串在主串中出现的位置确实就是这个计算后的位置，大家也可以自己找一个例子然后对照代码验算一遍，看看是否符合:rabbit:

🦏时间复杂度分析

看完了BF暴搜的执行流程，接下来我们分析一下其时间复杂度为多少，继而更加明确这个算法的性能

• 从代码和算法图演示可以看出，这个算法确实是简单且易于理解，但是效率却不高，主要原因就是主串i在若干字符的比较相等后，若是有一个字符不匹配，就需要回溯【i - j + 1】。该算法在最好情况下的时间复杂度为O(n * m)，即主串的前m个字符刚好等于模式串的m个字符。在最坏情况下的时间复杂度为O(n * m),也就是我们刚才的那种，需要均遍历完两个串才可以找到匹配的子串所在的位置
• 对于时间复杂度的话，我们是按照最坏来算法的，也就是O(n * m)，当然不会是O(n^2^)，毕竟也是找子串，并不是比较两个串相等

🤡KMP算法

好，讲完了BF暴力算法，接下去我们来说一说大名鼎鼎的KMP算法，相等大家都有所耳闻，这本文要重点讲解算法

• 首先讲一下它的来源：这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法

🎴KMP的思路分析

都把这个KMP捧得那么高，它究竟好在哪里呢，我们首先对KMP有一个整体性的算法分析，来了解一下这个算法究竟如何实现的

BF与KMP的算法图对比

• 先通过两张算法原理图带你对比着分析一下BF与KMP有什么不同

==BF算法==

==KMP算法==

KMP匹配流程简述

• 从上面的算法图示可以看出KMP并没有像BF那样回溯，再次回到主串的第二位开始匹配，而是另辟蹊径，然后根据已经匹配过的字符，去向后继续寻找匹配，减少了回溯的次数
• 那它是怎么知道前面那些字符已经匹配过了呢？已经匹配了多少呢？还有怎么知道具体从哪个位置开始匹配呢？我们带着这些问题继续看下去:mag:

🎴最长相等前后缀【前缀与后缀】

接下去我们来介绍一个概念，叫做前后缀，那有同学可能会记起我前阵子讲到过的后缀表达式

• 我们来看看什么叫做前缀与后缀，以及这个最长相等前后缀
• 刚才说到了后，那就先讲后缀

• 对于后缀的话，就是从后面往前面看，组成的长度字符，但是要除了第一位为止
• 对于前缀的话，也是一样的道理，我们俩看一下

• 可以看到，除了列出前缀以外，我还找出所要说的最长相同前后缀，也就是去前面找，有没有前缀和后缀相同的，有几个，那个这个最长相同前后缀就记几，若是没有，则记为0
• 那有同学问了，找出这个最长相同前后缀有什么用呢,这其实就是为我们下面所要讲的Next数组做铺垫

🎴Next数组的初步介绍【三种不同实现方式】

好，接下来我们就来说一说什么是Next数组，这里要注意听了❗，对于Next数组，是求解KMP的核心所在🐚

• 对于Next数组，它在写KMP算法时都是会被使用到，从物理层面来讲，我们上面通过最长相等前后缀所计算出的数字，可以直接用这些数字当做Next数组，去求解KMP
• 然后为什么会说到这里的Next数组会有三种不同的方式呢，这是因为许多人在写KMP算法的时候思路可能都不太一样，认为自己的这种Next数组看起来最直观，所以就有了三种Next数组，我还是习惯用直接通过最长相同前后缀找出来的这种
• 使用这种Next数组碰见==冲突位置==后呢，就找到它的前一位，通过前面一位的Next数组所对应的值，然后跳到这个值所在这个数组中的下标【数组下标当然从0开始】，==然后从这个位置开始匹配就行了==，这回对我上面KMP算法简介时画的算法图有了一个初步地了解了吧
• 我们通过下面这张图来看看其他两种Next数组

• 可以看到，对于第二种Next数组，是将第一种我们直接求出来的Next数组向后移动一位，然后呢将这个第一个空出来的位子置为-1，就形成了第二种Next数组，这种用的人也蛮多的。这种Next数组若是失配了之后，不是找前一位，就是找冲突的那一位，直接找那一位所在的Next数组所对应的值，为什么？因为你后移了一位呀！！！所以直接找这个冲突位置就可以了。接着跳到那个位置继续查找便可
• 第三种呢，就是将每一个位置上的数字-1，很直观。这个怎么找呢？也是找前一位，不过前面-1了，在+1加回去，又变回2了，然后就和第一种一样。我也不知道为何要这么干。。。可能是为了好玩吧，哈哈:smile:

对于上面的三种Next数组形式，你使用哪一种都可以，萝卜青菜各有所爱:heart:

🎴如何求解Next数组【详细算法图解】

初步了解了这个Next数组后，我们只是了解了这个具体回溯流程，但是如何使用代码去求解这个Next数组呢？这还是==谜==:mag:

• 如何去求解这个Next数组呢，我将整体的步骤分为了4步，分别是
  
  ①初始化
  ②求解前后缀不相同的情况
  ③求解前后缀相同的情况
  ④更新Next数组对应位置的值
  

分步代码分析

首先，我们先进行一个初始化操作

• 我们要将这个求解Next函数的过程单独封装为一个函数，函数的返回类型为void，参数是我们要匹配的子串，以及这个数组
• 接下去我们需要两个指针，一个指向子串的前缀末尾，一个指向子串的后缀末尾，有关前后缀的概念我在上面讲过了，若有点以往，再上去看看。首先将这个指向前缀的指针指向0下标所在位置，然后指向后缀的指针指向1下标所在位置，因为它们两个位置上的数我们需要进行一个匹配比较，所以不可以在同一个位置上，前缀在前，后缀在后
• 然后这个next数组的第一个下标所指的位置为什么要置为0呢，这是因为第一个位置的最长相等前后缀一定为0，没有后缀与其相同，所以直接置为0即可:zero:

void GetNext(SqString t, int next[])
{		//i : 后缀末尾	j : 前缀末尾
	int j = 0;
	next[0] = 0;
	for(int i = 1;i < s.size(); ++i)
}

接下去就是当这个前后缀不相同的情况

• 这个时候我们要模拟和主串出现了一个匹配冲突的场景，然后让前缀末尾j进行一个向前的回退，这个j其实不仅仅指的是前缀末尾，其实也可以是这个最长相同前后缀的长度，==因为它在这个一直回退的过程中其实就在寻找前后缀是否匹配了==
• 但是这个回退是有底线的，我们平常里经常会说【退一步，海阔天空】，但是呢，退让也是要有限度的，不可以一直退，否则的话就会超出数组的前边界了，因此还有设定条件【j > 0】，若是【j = 0】的话，这个数组的值就成了next[-1]，此时便造成数组的访问越界
• 具体代码如下

while(j > 0 && s[i] != s[j])
{
	j = next[j - 1];
}

• 这里是【while】而不是【if】，这一点要注意了，很多同学就在这里翻车:car:了，你前缀在向前回退的时候难道只会回退一次就不再退了吗？虽然【退一步，海阔天空】但是有的时候只退一步还真不太够，所以要使用while循环封装起来，模拟这个持续回退的过程，【退、退、退】:point_left:

接下去是要考虑的是前后缀相同的情况

• 当这个前后缀相同的时候，就需要去更新前缀末尾j的值，使其向后移动一位，看看下一位是否也相同

if(s[i] == s[j])	j++;

然后就是更新Next数组

next[i] = j;

• 这个更新next数组的语句，是写在一个大的for循环里的，在这个for循环体内，执行的流程就是我们上面所介绍的步骤，首先就是判断前后缀不同然后持续回退的过程，若是相同了，则执行下面相同的情况，使前缀末尾++，若是j到达数组最前面，则直接跳出循环，这个时候一定不会满足【s[i] == s[i]】，因此就会跳到我们这里所说的更新Next数组的值，这就是执行的大体流程
• 为什么将这个next数组当前的数的值更新为j的值的，上面说过，j不仅仅代表的是前缀末尾，而且代表的还是==i包括i之前最长相同前后缀的长度==，至于为什么，我们通过算法图解来模拟一下你就明白了

整体代码展示

在这之前先展示一下整体代码

void GetNext(SqString t, int next[])
{		//i : 后缀末尾	j : 前缀末尾
	int j = 0;
	next[0] = 0;
	for(int i = 1;i < s.size(); ++i)
	{
		//1.前后缀不相同
		while(j > 0 && s[i] != s[j])
		{
			j = next[j - 1];
		}
		//2.前后缀相同
		if(s[i] == s[j])	j++;
		//3.更新next数组的值
		next[i] = j;
	}
}

算法图解模拟Next数组求解过程

• 首先第一步，进行一个数组0位置以及i和j的初始化

• 然后开始比较，【s[i] == s[j]】，所以j++，更新前缀末尾的位置
• 然后呢继续更新当前字符a所对应的next数组的值，也就是j当前所在数组的下标位置【1】

• 一个for循环整体走完了，然后又进入下一个for循环，此时i++，继续扫描下一个位置

• 此时a[i] != a[j]，因此进入while循环，实行j的一个回退，next[j - 1] = 0,所以退到下标为0的位置，此时呢【j = 0】了，便不满足这个while循环的条件，便跳出循环

• 这个时候也不会进入if条件的判断，因为【s[i] != s[j]】，所以回去更新next数组的值，j此时的下标为0，因此字符b的next数组下标值为【0】

• 此时又再次进入了第三次循环，i++，然后进行一个比较，【a == a】，所以满足前后缀相等的情况

• 此时j++，更新前缀末尾的指针j
  
• 然后便更新next数组的值，j此时的下标为1，所以当前字符a的next数组值便为1

• 然后可以看到【a == a】，所以满足前后缀相同的情况

• 此时更新next数组的值，j的下标为2，因此当前i所指字符a的next数组下标值为2
• 其实这个时候你就可以发现了，next数组的值和这个j当前所在下标的值是完全吻合的，所以我在上面说到的==j不仅仅是前缀末尾，而且还是当前i所指位置最长相等前后缀的长度==，一步步看下来相信你应该有所领会📕

• 然后继续来看，i++之后，【a[i] != a[j]】，所以进入while循环，实行j的回退

• next[j - 1] = 1，所以退到下标为1的位置，可以看到，此时依旧是【a[i] != a[j]】，所以继续实行j的回退

• next[j - 1] = 0，退到下标为0的位置。但此时【j = 0】，所以跳出while循环，然后更新next数组的值，此时j 所在下标为0，所以字符f所对应的next数组值变为0

• 最后i++，便超出了数组的边界，所以退出整个for循环，然后结束程序

• 最后求出了next数组的所有值，你学会了吗❓

🎴Next数组的另一种解法

上面说到过Next数组有三种不同的形式，在市面上各种教材里，也都有涉及到，我们这里再来讲一种，就是将求出来的前缀表统一减一后的操作在这里插入代码片

• 刚才的前缀表是【0 1 0 1 2 0】，统一减一后就是【-1 0 -1 0 1 -1】
• 我们还是延用刚才的i和j，但是初始化时指向的位置不一样了，初始化时要将这个j 置为-1,然后将当前next数组第一位的值设为j，思想还是一样j不仅仅是前缀末尾，还是最长相等前后前后缀的长度，即当前next数组所指位置的值

int j = -1;
next[0] = j;

• 然后在循环开始的时候初始化i的值，这个时候i要从1开始，因为后面我们需要对s[i] 和 s[j + 1]进行比较，==前缀末尾j 和后缀末尾i 在比较的时候是不可以再同一个位置上的==

for(int i = 1; i < s.size(); i++) { // 注意i从1开始

• 在回退的时候，去判断【s[i] != s[j + 1]】，而且在回退的过程中j也就不可以超出数组的边界，但是这里j可以取0，因为next[j] 为 next[0]成立,但是当【j == -1】时间，next[j] 为 next[-1]便不成立了

while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
    j = next[j]; // 向前回退
}

• 接着就是相同前后缀的情况，思想还是一样，若是相同将前缀末尾j的值++便可
• 最后更新这个next数组的值，这个是不变的，还是j所在下标位置

if (s[i] == s[j + 1]) { // 找到相同的前后缀
    j++;
}
next[i] = j;

展示一下整体的代码

void GetNext(SqString s, int next[]){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

一样，使用算法图解展示一下流程

• 可以看到，求出用此方法求解出来的next数组和第一个方法对比，就是整体-1
• 你可以对照以上的算法图自己模拟一下，我就不细讲了

🎴KMP算法代码

讲完了第二种Next数组的求解方法，接下去便给出KMP算法的代码，是基于第二种Next数组来的

void GetNext(SqString s, int next[]){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

int KMP(SqString s, SqString t)
{
	int next[10],i = 0, j = 0;
	GetNext(t, next);
	while(i < s.length && j < t.length)
	{
		if(j == -1 || s.data[i] == t.data[j]){
			i++;
			j++;
		}
		else j = next[j];
	}
	if(t > t.length)
		return (i - t.length);
	else
		return -1;
}

🎴LeetCode习题深入

通过上面对KMP算法的一系列分析，接下去我们通过一道LeetCode习题来练练手

原题传送门

题目描述

找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

• 题目的意思就是在一个主串中寻找子串第一次出现的位置，其实就是我们所要讲的串的模式匹配问题
• 找到了，便返回第一个匹配字母的下标；没找到，返回-1

思路分析及代码展示

然后我们来分析一个如何去求解这道题

• 首先最直观的，就是BF暴力解法，直接上代码

class Solution {
public:
    int strStr(string haystack, string needle) {
        int i = 0,j = 0;
        while(i < haystack.size() && j < needle.size())
        {
            if(haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                i = i - j + 1;
                j = 0;
            }
        }
        if(j == needle.size())
            return i - needle.size();
        else
            return -1;
    }
};

• 可以看出，虽然能AC，但是效率并不是很高，我们要的是==最优解==

• 然后再来一个，嗯。。。很快的方法🐕

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

• 是的，这也是可以AC，直接调用find库函数就行，返回的就是子串在主串中第一次出现的位置

但是这起不到训练的效果，我们主要还是来看一下KMP算法

• Next数组肯定要使用到，上面讲了那么多种方法，这里要注意的是，在赋值出去的时候记得加引用，不然Next数组的值没有真正给到子串
• 主函数中，首先需要去判断特殊情况，若是子串的长度为0，则主串中不会有出现与其相等的子串。然后使用子串needle的长度去开辟维护数组，做到大小适中。使用GetNext将Next数组中的值给到子串needle中，然后就可以遍历主串去匹配了
• 从代码中可以看到，匹配的过程和Next数组的求解过程很是相似，因为我们在求解Next数组的时候，就是模拟主串与子串匹配的过程，其实这个应该是获取Next数组仿照主串匹配子串的代码，哈哈
• 然后这里有一点是当子串匹配结束之后，表明匹配成功了，此时要返回位置使用【i - needle.size() + 1】即可，因为i是从0开始遍历的，所以要加上个1

class Solution {
private:
    void GetNext(string &s, int* next)
    {
        int j = 0;
        next[0] = 0;
        for(int i = 1;i < s.size(); ++i)
        {
            //1.判断前后缀不相同的情况
            while(j > 0 && s[i] != s[j]){
                j = next[j - 1];
            }
            //2.判断前后缀相同的情况
            if(s[i] == s[j])    j++;
            //3.更新next数组的值
            next[i] = j;
        }
    }
public:
    int strStr(string haystack, string needle) {
        if(needle.size() == 0)
            return 0;
        int next[needle.size()];
        GetNext(needle, next);

        int j = 0;
        for(int i = 0;i < haystack.size(); ++i)
        {
            while(j > 0 && haystack[i] != needle[j])
            {
                j = next[j - 1];
            }
            if(haystack[i] == needle[j])    j++;
            
            if(j == needle.size())
                return (i - needle.size() + 1);
        }
        return -1;
    }
};

• 从执行结果来看，KMP的效率还是很可观的
• 有关Next数组，因为上面还讲到了另一种求解方式，因此对于这种方法也是有类似的代码，一样给出大家参考

class Solution {
public:
    void getNext(const string& s, int* next) {
        int j = -1;		//此时的Next数组初始j置为-1
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { //Next数组整体-1，此处的子串needle长度也需要-1
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

🎴KMP算法复杂度分析

看了这么多，知道了使用KMP算法去匹配串效率比BF暴搜要高，对于BF算法，时间复杂度是O(m * n)，那对于KMP算法，它是时间复杂度是多少呢？空间复杂度又是多少呢？

• 首先来说说空间复杂度，因为需要维护一个Next数组，因此空间复杂度为O(n)
• 然后对于复杂度的话，我们设主串s的长度为n，子串t的长度为m，在KMP算法中求Next数组的时间复杂度为O(m)，在后面匹配中因目标串s的下标i不减【即不回溯】，只需要子串通过Next数组不断回退到目标位置，对指定位置开始匹配即可，因此对于比较次数的话可记为n，所以KMP算法的平均时间复杂度为O(n + m)，优于BF暴搜
• 但是不等于任何情况下KMP算法都优于BF算法，当子串的next数组中next[0] = -1，而其他值均为0，==也就意味着每个字母的最长相同前后缀均为0，也就是子串中每个字母都不一样==。此时在与主串匹配时发生冲突时。便无法通过Next数组寻找到对应的位置开始定标匹配，只能像BF算法那样一一往后做匹配，也就退化成了BF算法

可能讲得有些浅显，具体大家想深入了解的可以看看这篇文章 KMP时间复杂度分析

📚参考文献和资料

Carl —— 代码随想录

李春葆 —— 数据结构教程（第五版）

百度百科 —— KMP算法

KMP时间复杂度分析

✒总结与提炼

看完了BF暴搜和KMP算法，你对模式串的匹配问题有一个大体的了解了吗？

• 对于BF暴力搜索，就是使用两个指针去遍历主串和子串，若是找到不匹配的，则更新主串的位置，一一向后遍历查找，子串继续从从开始遍历，回溯的次数比较多，显得会冗余一些
• 而对于KMP算法呢，虽然需要维护一个数组来存放子串的Next数组值，但是有了这个Next数组，起到的确是很显著的效果，在子串与主串匹配冲突时，对于前缀末尾的指针会根据Next数组的值实现一个回退的效果，当然，不同的Next数组回退的方法不同。我们也介绍了三种Next数组，因为随着写KMP的人越来越多，生成Next数组的方式也是五花八门，但是无论这个Next数组是怎样的，KMP算法匹配模式串的本质不会改变

对于模式串的匹配算法，其实不止BF和KMP这两种，还有很巧妙的==Sunday和BM算法==，之后有机会再做更新📰