图解KMP算法,带你彻底吃透KMP

2024-03-04

模式串匹配——KMP算法

KMP算法一直是一个比较难以理解的算法,本篇文章根据dalao们的Blog,结合自己的思考,对于KMP算法进行一个比较详细的解释。

由于博主本人水平有限,难免会出现一些错误。如果发现文章中存在错误敬请批评指正,感谢您的阅读。

字符串模式匹配介绍

相信学习过数据结构与算法的同学一定不会对字符串感到陌生,字符串的逻辑结构与线性表很类似,不同之处是字符串中的元素都是字符。对于字符串这一数据结构,寻找字符串中子串的位置是最重要的操作之一,查找子串T位置的操作通常称为串的模式匹配。而KMP算法就是一种字符串模式匹配算法,在介绍KMP算法之前,我们首先了解以下朴素的模式匹配算法是怎样进行的。

朴素的模式匹配算法

假设我们的主串S=“goodgoogle”,子串T=“google”,我们需要在主串S中找到子串T的位置,比较朴素的想法是用两个指针(指针其实也就是下标 i 和 j )分别指向主串S和子串T,如果两个指针指向的元素相同则指针后移,不相同则需要回退指针(主指针回退到上次匹配首位的下一个位置,子指针回退到开头位置),重复进行上述操作直到主指针指向主串S末尾,即如下所示:

① 如图 从主串S的第一位开始,主串S与子串T的前3位都匹配成功,第4位匹配失败,此时将主串S的指针 i 退回到第2位,子串的指针 j 退回子串开头,即从S[1]开始重新匹配。

kmp1

② 主串S从第2位开始与子串T匹配,第一步就匹配失败,将主指针 i 退回第三位S[2],子指针 j 指向开头,继续匹配。

kmp2

③ 同步骤②,第一步就匹配失败,将主指针 i 移动到第四位S[3],子指针 j 指向开头,继续匹配。

kmp3

④ 还是第一步就匹配失败,将主指针 i 移动到第五位S[4],子指针 j 指向开头,继续匹配。

kmp4

⑤ 到步骤5终于第一步能够匹配上,从S[4]开始指针 i, j 依次向后移动,六个字母全部匹配上,匹配成功!

kmp5

根据上面的步骤,我们可以得出朴素模式匹配算法的代码如下所示:

int find_sub_string(string s, string t)
{
	int i = 0, j = 0;	//初始化两个指针
    while(i<s.size() && j<t.size()){
        if(s[i] == t[j]){
            i++;	//如果两个指针指向的字符相等
            j++;	//则将两个指针向后移动
        }
        else{
            i = i - j + 1;	//匹配失败,i退回到上次匹配首位的下一位
            j = 0;			//j退回到子串首位
        }
    }
    if(j<=t.size()){	//j走到子串末尾说明匹配成功
        return i - j;	//匹配成功返回主串中子串出现的第一位
    }
    else 
        return -1;		//匹配失败,返回-1
}

既然是朴素(暴力)解法,那必然存在时间复杂度的问题,我们不妨分析以下上述算法的时间复杂度。

最好的情况是一开始就匹配成功了,如主串S为”googlegood”,子串T为”google”,此时的时间复杂度为O(m)(m为子串T长度)

那么最坏的情况是什么呢?最坏的情况就是每次不成功的匹配都发生在子串T末尾,就如书中的例子,主串S为=“00000000000000000000000000000000000000000000000001”,子串T为=“0000000001”,推导一下可得此时的时间复杂度度为O((n-m+1)*m)(n为主串S长度)。

而在计算机中对字符的存储采用的是ASCII码,字符串可以看成是许许多多个0和l组成,因此这种最坏的情况是很可能出现的,在计算机的运算当中,模式匹配操作可以说是随处可见。这样看来,这个如此频繁使用的算法,朴素做法显得太低效了。

KMP算法

为了避免朴素算法的低效,几位计算机科学家辈D.E.Knuth、J.H.MorTis和V.R.Pratt发表了一个模式匹配算法,可以一定程度上避免重复遍历的问题,该算法就是大名鼎鼎的KMP算法

从暴力匹配到KMP

要理解KMP算法的原理,我们首先需要批判一下朴素算法中有哪些做的不好的地方。

我们将之前的朴素算法的匹配过程合起来看如下面的图所示:

kmp6

我们可以发现,在②、③、④步骤中,主串S的首字符与子串T的首字符均不等。我们仔细观察可以发现,对于子串T”google”来说,首字母”g”与后面的两个字母是不相等的,而在步骤1中主串S与子串T的前三个字符相等,这就意味着子串T的首字符”g”不可能与主串S的二、三位相等,故上图中步骤②、③完全是多余的。

也就是说,如果我们知道子串T的首字符”g”与后面两个字符不相等(此处需要进行一些预处理,这是后面的重点),我们就不需要再进行、③步操作,只保留①、④、⑤步即可。如图所示,①、②、③步分别对应朴素算法的①、④、⑤步。

kmp7

从上面这幅图我们可以惊喜地发现,在使用朴素算法进行匹配时,主指针 i 需要进行一些回退;而在知道了子串T的一些性质后,主指针 i 不需要再进行回退,只需一直往前走就行,这样就节省了一些时间开销。

你或许还会有疑问,主指针 i 是不需要回退了,但为啥我的子指针 j 还要一直回退到开头呢,有没有办法避免这样呢?

当然是有的,我们再举一个例子,假设主串S=“abcababca”,子串T=“abcabx”,那我们采用朴素算法在进行模式匹配的步骤如下所示:

kmp8

由之前一个例子的分析可知由于子串T的首字母”a”与之后主串S上的字母”b”、”c”不等,故步骤②、③均是可以省略的。

又因为子串T的首位”a”与子串T第四位的”a”相等,子串T第2位的”b”与子串T第5位的”b”相等。而在步骤①中,第四位的”a”与第五位的”b”已经与主串S中的相应位置比较过了是相等的。因此可以断定, 子串T的首字符“a”、第2位的字符“b”与主串S的第4位字符和第5位字符也不需要比较了,肯定也是相等的。所以步骤④、⑤这两个比较得出字符相等的步骤也可以省略。

所以在这个例子中我们模式匹配的流程为:

kmp9

在这个例子中我们发现,在得知了子串T中有相等的前后缀之后,匹配失败时子指针不需要回退到开头处,而是回退到相等前缀的后一个位置。

对比两个例子中朴素做法与改进做法的差别,我们可以发现这两种方法的相同点为都是依靠两个指针 i, j 的移动对比来实现字符串模式匹配,不同之处在于在改进做法中主串S的指针 i 不需要进行回溯,子串T的指针 j 会根据子串T中的最长相等前后缀来进行回溯,这样就省去了一些不需要的回溯步骤,从而降低了时间复杂度。

上面就是从暴力模式匹配算法到KMP算法的推导过程,下面我们再介绍KMP算法的具体原理。

KMP算法原理

在学习KMP算法的原理之前,我们需要先学习前后缀和前缀表这个概念。

字符串前缀,指串左部的任意子串,比如说有一个长度为5字符串 x=”ababc”,其中”“(空串),”a”,”ab”,”aba”,”abab”,”ababc”都是 x 的前缀;同理”“(空串),”c”,”bc”,”abc”,”babc”,”ababc都是 x 的后缀。

前缀表,顾名思义,前缀表是一张表(或者直接理解为一个数组),表中记录的是字符串中的每个子串的最大相等前后缀(它自己不算)的长度,这个概念有点长也有点抽象,我们举一个例子来具体说明一下。

设字符串T=“aabaaf”,我们求一下T的前缀表(用一个数组名为next的数组表示)。

  1. 第一个子串是t0=“a”,易知该子串没有不是它自己的前缀和后缀,故next[0]=0

  2. 第二个子串是t1=“aa”,”a”是该子串的前缀,也是该子串的后缀,故next[1]=1

  3. 第三个子串是t2=“aab”,该子串的后缀中一定会有”b”,不是它自己的前缀中一定不含有”b”,则其没有相等的前后缀,故next[2]=0

  4. 第四个子串是t3=“aaba”,该子串的最大相等不是它自己的前后缀为”a”,长度为1,故next[3]=1
  5. 第五个子串是t4=“aabaa”,该子串的最大相等不是它自己的前后缀为”aa”,长度为2,故next[4]=2

  6. 第六个子串是t5=“aabaaf”,该子串的后缀中一定会有”f”,不是它自己的前缀中一定不含有”f”,则其没有相等的前后缀,故next[5]=0

所以我们能得到字符串T的前缀表为:

j 0 1 2 3 4 5
T a a b a a f
next 0 1 0 1 2 0

那既然我们得到了前缀表,前缀表在KMP算法中的作用是什么呢?其实前缀表决定了子指针j在匹配失败时回溯到的位置

结论:前缀表是用来回退的,它记录了模式串(子串)与文本串(主串)不匹配的时候,模式串应该从哪里开始重新匹配。

我们举个例子来说明这个结论,假设主串S=“aabaabaaf”,子串T=“aabaaf”,我们已经求出了子串T的前缀表,采用KMP算法匹配的流程如下:

kmp10

从上面的流程可以看到,在子串T的某一个字符 t[ j ] 处匹配失败时,我们需要查找该字符前面的那个子串的最大相等前后缀的长度,即 next[j-1],然后使 j 指针退回到 next[j-1],i 指针不变,继续匹配,不断重复这个操作知道匹配成功或者j指针大于等于子串T长度。在这里 j 指针之所以退回到next[j-1]的位置我们可以根据例子思考一下,字符”f”前面的子串为”aabaa”,该子串的最大相等前后缀为”aa”,而该子串的后缀”aa”已经与s[3]s[4]比较过是相等的,那么子串T的前缀就一定是与s[3]s[4]相等的,不需要比较,因此我们的j可以从前缀的后面第一个字符开始匹配,而前缀的长度为next[j-1],所以 j 应该回退到next[j-1]。

在理解了前缀表及其作用之后,KMP算法就可以整体上分为两步:

一、计算前缀表。

二、根据前缀表移动两个指针进行匹配。

下面我们给出KMP算法的代码实现如下:

void init(string s, int next[])		//这个函数对字符串s进行预处理得到next数组
{
	int j = 0;
	next[0] = 0;	//初始化
	for(int i = 1; i&lt;s.size(); i++){	//i指针指向的是后缀末尾,j指针指向的是前缀末尾
		while(j>0&&s[i]!=s[j])	j = next[j-1];	//前后缀不相同,去找j前一位的最长相等前后缀
		if(s[i]==s[j])	j++;	//前后缀相同,j指针后移
		next[i] = j;	//更新next数组
	}
}

上面是计算模式串的前缀表next的代码,其流程见注释。

得到了next数组后,我们进入匹配查找的阶段。

int init(string s, string t)	//这个函数是从s中找到t,如果存在返回t出现的位置,如果不存在返回-1
{
	if(t.size()==0)	return 0;
	get_Next(t, next);
	int j = 0;
	for(int i = 0; i < s.size(); i++){
		while(j>0&&s[i]!= t[j])	j = next[j-1];	
		if(s[i]==t[j])	j++;
		if(j==t.size())	return i - t.size() + 1;
	}
	return -1;
}

下面我们来做一道KMP模板题

用刚刚给出的代码模板可以得出这道题的代码如下:

#include<bits/stdc++.h>
using namespace std;
string s,t;
int nxt[1000005];  //   next前缀表
int main(){
    cin>>s>>t;
    for(int i=1,j=0;i<t.size();i++){       // 这个函数对字符串s进行预处理得到next数组
        while(j>0&&t[i]!=t[j])j=nxt[j-1];  // 前后缀不相同,去找j前一位的最长相等前后缀
        if(t[i]==t[j])j++;                 // 前后缀相同,j指针后移
        nxt[i]=j;                          // 更新next数组
    }
    for(int i=0,j=0;i<s.size();i++){
        while(j>0&&s[i]!=t[j])j=nxt[j-1];
        if(s[i]==t[j])j++;
        if(j==t.size()){
            cout<<i-t.size()+2<<'\n';
            j=nxt[j-1];
/*
 * 注意此处不能直接使用之前的kmp函数,
 * 因为模式串(子串T)在字符串(主串S)中多次出现,
 * 所以需要对kmp函数进行小小的修改,
 * 在匹配完成即 j==n 之后将 j 指针指向 nxt[j-1] ;
 * 
 * 且该题目要求输出下标从1开始。
*/
       	}
    }
    for(int i=0;i<t.size();i++)cout<<nxt[i]<<' ';
}

总结

KMP算法主要应用于字符串模式匹配,其核心思想在于使用前缀表从而实现在不匹配时利用之前已经匹配过的信息来减少回溯的过程。理解KMP算法的关键在于理解前缀表的生成,这部分可以手推几次应该就能理解。