一文看懂KMP(看毛片)算法

2021/5/11 20:28:58

本文主要是介绍一文看懂KMP(看毛片)算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一文看懂KMP算法

KMP是一种模式匹配算法。常用于在一个较长的字符串中查找一个较短的字符串。通常称较长的字符串为主串,较短的待匹配的字符串为模式串

比如给定一个主串S = ababacd,一个模式串P = abac,那么最终能够在主串中成功匹配到模式串

image-20210511104025001

通常,针对某一些算法问题,我们可以首先考虑一个暴力的解法,随后通过寻找规律,来省略掉一些无效的步骤,从而完成优化。

对于字符串匹配,很容易想到的暴力解法就是使用双指针。

如主串S的长度为n,模式串P的长度为mn > m)。定义指针iji初始指向主串的第一个位置,j初始指向模式串的第一个位置。

我们先假设S中包含了P,则在[1, n]区间内(下标从1开始),一定存在一个位置i,是S匹配P的起始位置。

S = ababcdP = abac,根据上图,我们一眼就能看出,S中包含了P,且起始位置是3。

所以,我们只需要在[1, n]区间内枚举i,并与P比较,若以某一个i为起点,能够完整匹配P,则找到答案。

我们比较主串的S[i]和模式串的P[j]

  • 若二者相等,则ij都往后移动一位,继续比较S[i]P[j]

  • 若二者不等,则主串中当前位置为起点无法匹配

    将起点往后移一位(i从2开始),继续比较

最终在i = 3为起点时,成功匹配

暴力解法写成代码如下

#include<iostream>
using namespace std;

const int N = 1e6 + 10, M = 1e5 + 10;
char s[N], p[M];

int main() {
	int n, m; // 主串S和模式串P的长度
	cin >> n >> m;
	// 读入主串S和模式串P, 下标都从1开始
	cin >> s + 1 >> p + 1;

	// 枚举 i = [1, n], 尝试匹配
	int i, j;
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= m; j++) {
			if(s[i + j - 1] != p[j]) break;
		}
		if(j == m + 1) printf("%d ", i); // 匹配成功, 打印起始坐标
	}
	return 0;
}

暴力解法i最多从1移动到n,每次尝试匹配时,j最多会移动m - 1次,所以暴力解法的时间复杂度为O(n×m)

那么KMP算法是怎么优化的呢?KMP采用了一种很巧妙的方法,比如上面的S = ababacdP = abac,当我们进行到这一步时

发现S[i] = bP[j] = c不匹配,但我们能不能利用一下前面已经匹配了的aba呢?答案是可以的,我们观察可以发现,已经匹配的aba,其前缀a和后缀a是相同的,我们可以不用回溯指针i,而是移动下面的模式串P

上面的操作,取决于已匹配的字符串中,前缀和后缀相等的最大长度

比如对于字符串aba,其所有可能的前缀为{a,ab}(不包含其本身),而其所有可能的后缀为{a,ba}

前缀集合后缀集合的交集,结果为{a},则对于aba,前缀和后缀相等的最大长度就是1。

再比如,对于字符串ababa,其所有可能的前缀为{a, ab, aba, abab},其所有可能的后缀为{a, ba, aba, baba}

前缀集合后缀集合的交集为{a, aba},其中长度最大的是aba,所以对于ababa,前缀和后缀相等的最大长度就是3。

对于一个长度为n的字符串,存在一个最大的k(k < n),使得该字符串的前缀[1,k]和后缀[n-k+1, n]相等。当然,当不存在相等的前缀和后缀时,k为0。

这个相等的前缀与后缀有什么作用呢?

考虑如下情况,当我们匹配了一定的长度时,然后发现S[i]P[j]不相等,此时我们可以利用前面已经匹配的部分,将模式串P一次性往右移动多个位置,而不移动指针i,那么P需要一次性移动多少呢?这就需要用到上面提到的前缀后缀相等的最大长度这个概念了

假设上图中已经匹配的绿色的部分,其前缀后缀相等的最大长度为k,如下图标为粉色的部分

很明显,我们可以将P串直接往右挪动(实际是回溯指针j,将j往左移动,移动到P串中粉色部分的最右端),使得上下的粉色部分进行对齐,然后接着继续比较S[i]P[j]即可

由于,SP可能在任何一个位置出现不匹配,那么我们对P的每个位置,都需要求解以该位置为终点的前缀后缀相等的最大长度,这也是求解KMP算法中最核心的next数组。

比如对于P = ababac,其next数组求解出来结果如下

下标123456
001230

解释:

  • next[1] = 0,因为前缀后缀的长度必须要小于字符串本身,所以next[i]一定是小于i的,而next[1] = 0也就表示了:a这个字符串,由于不存在前缀与后缀,其前缀与后缀相等的最大长度为0
  • next[2] = 0,观察ab这个字符串,其可能的前缀只有一个a,可能的后缀也只有一个b,前缀集合与后缀集合的交集为空集。即,不存在相等的前缀和后缀,所以next[2]也为0
  • next[3] = 1,观察aba这个字符串,其前缀集合为{a, ab},后缀集合为{a, ba},二者的交集为{a},所以相等的前缀后缀的长度就是1
  • next[4] = 2,观察abab,前缀集合为{a, ab, aba},后缀集合为{b, ab, bab},二者的交集为{ab},这个相等的前缀和后缀的长度就是2
  • next[5] = 3,观察ababa,前缀集合为{a, ab, aba, abab},后缀集合为{a, ba, aba, baba},二者的交集为{a, aba},其中最大的长度就是3
  • next[6] = 0,观察ababac,前缀集合为{a, ab, aba, abab, ababa},后缀集合为{c, ac, bac, abac, babac},二者的交集为空集,不存在相等的前缀和后缀,所以next[6]为0

为什么我们的数组下标从1开始,这是为了更方便地处理边界问题,稍后展示代码时就能明白了。

接下来,有了next数组,KMP算法就变得非常简单了,下面进行代码展示,以s表示主串,p表示模式串,s的长度为np的长度为m,且n > m

/*1*/	for(int i = 1, j = 0; i <= n; i++) {
/*2*/		while(j > 0 && s[i] != p[j + 1]) j = next[j];
/*3*/		if(s[i] == p[j + 1]) j++;
/*4*/		if(j == m) {
/*5*/ 	    	// 匹配成功, 返回主串的起始坐标i, 下标从1开始
/*6*/   		printf("%d ", i - m + 1); 
/*7*/   		j = next[j]; // 继续后续可能的匹配
/*8*/		}
/*9*/	}

我们的下标i从1开始,j0开始,每次比较s[i]p[j + 1]

第2行的含义是,当j > 0,即先前已经有部分字符串匹配上,且这次没有匹配上时,回溯j,将j置为next[j]。由于此时j指向的是p串中已匹配部分的最后一个位置,next[j]则表示以当前j为终点的字符串,其相等的前缀和后缀的最大长度,这恰好能和上面我们讲解的next数组的定义对上。然后将j置为next[j],结合上面的图来看,就是将j放到了p串中粉色部分的最后一个位置,则下次比较时,应当比较s[i]p[j + 1]

这就是我们代码为什么要将j从0开始枚举,而i从1开始,保持ij错开一位,而每次比较s[i]p[j + 1]

当第2行的while循环结束时,

  • 要么是j被置为0了:这种情况就是p串需要从第一位和s串进行比较(从头开始)
  • 要么是s[i] == p[j + 1]:这种情况就是当前位置匹配上了

第3行,若当前位置能够匹配上,则将j后移一位

第4行,若j == m,则说明p串已经匹配到最后一位了(如果当前成功匹配了s[i]p[m],则完成匹配,此时j + 1 = m,j = m - 1,由于进入了第3行的if块,进行了j++,所以最后j变为了m),匹配完成,打印出此时s串中匹配的起点,表示找到了一个符合条件的匹配。并将j置为next[j](往右挪动p串),继续进行后续可能的匹配。

对于KMP的核心流程,上面的解释已经十分清楚了,然而上面的求解过程需要基于next数组,所以我们仍然需要对p串进行预处理,求出其next数组。好消息是,求解p串的next数组的过程,和上面的算法流程十分相近!

我们可以对p串自身进行上面的匹配过程!

由于next[1] = 0,所以我们从第二位开始对p串进行匹配,代码如下

	for(int i = 2, j = 0; i <= n; i++) {
        // 错开一位进行匹配, 每次匹配 i 和 j + 1 位, 第一次则匹配 2 和 1
        // 当前面有匹配上的部分时, 看看当前位是否匹配, 若不匹配, 则回溯 j 
        while(j > 0 && p[i] != p[j + 1]) j = next[j]; 
        if(p[i] == p[j + 1]) j++; // 该位匹配上了, 则 j 往后移动一位
        next[i] = j; // 当前位置的 next[i] = j
    }

开始时,i = 2, j = 0,我们仍然比较p[i]p[j + 1],此时若p[2] = p[1],则j++,随后next[i] = j

则此时next[2] = 1

更通常的,对于next[i],如果在当前位置能够匹配上,即p[i] = p[j + 1],则next[i] = next[i - 1] + 1

如果当前位置无法匹配上,即p[i] != p[j + 1],则需要将j置为next[j](由于i总是大于j的,而每次得到next数组的值时,都是通过对next[i]进行赋值完成的。所以此时next[j]一定在先前就被求解出来了),即回溯j,即右移下面的p串,随后继续比较p[i]p[j + 1],直到

  • 满足p[i] = p[j + 1],则当前next[i] = j + 1

  • j回溯为0,仍然p[i] != p[j + 1],即p[i] != p[1],则next[i] = 0

由上面的分析可见,求解next数组,与KMP的核心算法流程是一致的。我们通过让模式串p和它自身做模式匹配,求解出其next数组,随后使用pnext数组,完成主串s和模式串p的匹配。

至此,相信你已经领略到KMP算法的设计之精巧了。下面就尝试一道算法题来结束KMP的学习吧!

Acwing - 831: KMP字符串

或者

Leetcode - 28: 实现strStr()

其中Acwing - 831这道题目的题解如下

#include<iostream>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

char p[N], s[M];

int n, m;

int ne[N]; // 由于 C++ 中 next 变量已经在其他的头文件定义了, 所以这里将 next 数组命名为 ne

int main() {
    
    cin >> n >> p + 1 >> m >> s + 1; // 读入p和s时, 从下标为1的位置开始读入    
    // 先求解p串的next数组
    for(int i = 2, j = 0; i <= n; i++) {
        while(j > 0 && p[i] != p[j + 1]) j = ne[j]; // 回溯j
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    
    // 进行s串和p串的匹配
    for(int i = 1, j = 0; i <= m; i++) {
        while(j > 0 && s[i] != p[j + 1]) j = ne[j]; // 回溯j
        if(s[i] == p[j + 1]) j++;
        if(j == n) {
            // 匹配完成
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

参考链接:https://www.zhihu.com/question/21923021



这篇关于一文看懂KMP(看毛片)算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程