ACM 选手带你玩转 KMP 算法!

简介: ACM 选手带你玩转 KMP 算法!

大家好伐,我是侬们的帅蛋。


今天来学能让小儿止啼的 KMP,是不是很慌?


本来在本蛋的计划里,KMP 的顺序还是要往后放一下,但是架不住小婊贝催问。

640.png


那还说啥,直接安排!就今天,直奔字符串模式匹配!


你们的需求就是我肝的方向!上面的小老弟留言一次哪成,看着不像铁蛋粉

640.gif


这次保证安排的明明白白的,文章除了理解 KMP 算法的本质,拿去应付考试题也保证妥妥的!

640.png



字符串模式匹配
是字符串中最重要的操作之一,就是找模式串在主串中的位置


臭宝:呃,啥是主串,啥是模式串咧?

蛋蛋:如果你要找字符串 B 在字符串 A 中的位置,那么字符串 A 就是主串,字符串 B 就是模式串。可以理解主串就是大串,模式串就是小串。


字符串模式匹配算法有很多,但是要说提起字符串匹配,大家脑阔里的第一反应还是看毛片,呃,KMP 算法。


KMP 算法匹配字符串非常高效,但是原理有些复杂,学起来脑瓜子嗡嗡的,是学生时代学数据结构与算法绕不过去的坎儿。


不过不慌,这玩意本帅蛋门儿清。掏出你的卫生纸,呃,草稿纸,整活。

640.jpg


要学 KMP 模式匹配算法,首先先明白之前的匹配有多笨,所以我们先来看无脑流暴力匹配。


   暴力模式匹配



暴力模式匹配,无脑流的典型代表,没办法情况下的无冕之王。


假设主串的长度为 n,模式串的长度为 m,暴力模式匹配就是对主串的下标为 0 1 2 3 ... n - m 的元素作为模式串的开头,与模式串依次进行匹配,看有没有与模式串完全匹配的。


下面来看一个例子。

640.png


从上图可以看出,暴力匹配是在主串的长度下做模式串次匹配。


最好的情况就是从第 1 次开始就匹配成功,此时的时间复杂度就是 O(1)。

640.png

最坏情况的情况是,模式串每次都匹配到最后一个才发现和主串不同。比如主串是“aaaaab”,模式串是“aab”。

640.png


看上图,除了最后一次,其余的都是每次匹配到最后,才发现,啊,我们不一样。


这种情况下,上图中,模式串在前 3 次,每次都要匹配 3 次,并且不匹配,直到第 4 次,全部匹配,不需要继续移动,所以匹配的次数为(6 - 3 + 1)* 3 = 12 次。


由此可知,对于主串长度为 n,模式串长度为 m ,最坏情况下的时间复杂度为 O((n - m + 1) * m) = O(n * m)。


你看,暴力模式匹配这么低效,你能忍的了?


忍不了吧,来,看毛片!

640.png


   KMP 模式匹配



KMP 算法全称Knuth Morris Pratt是由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 三位大佬一起捣鼓出来的。


KMP 算法目的是为了快速的从主串中找到模式串,强调的是快,那咋快的呢?


那肯定是去掉暴力模式匹配中的”无脑“的部分。

640.png


上图是暴力模式匹配的前 2 步,有比较指针 i 和 j。


可以看到,在第 1 次匹配的时候,比较指针 i 和 j 走到了下标为 5 的位置发现不匹配的元素,然后进行第 2 次匹配,此时 i 回到了下标为 1 的位置。


如果继续匹配下去的话,你会发现比较指针 i 在频繁的来回折返跑,就像上图第 1 次匹配的时候 i 已经走到了 5,等到了第 2 次匹配的时候 i 又回到了 1。


这种动作叫做回溯,而造成暴力模式匹配效率低下的主要坏蛋就频繁的比较指针回溯。


KMP 算法做到的就是比较指针不回溯,仅仅是后移模式串。


我们接下来看,这具体是怎么实现的。下面这部分要慢一点,好好体会。


还是以主串 S = abcabcabda,模式串 T = abcabd 为例。

640.png

上图是模式串与主串的第一次匹配,在 i = 5,j = 5 的时候出现不匹配的元素,在此之前的元素都是匹配的。

640.png

观察一下模式串,你会发现在匹配的部分里,存在相同前后缀的部分。


那第二步的匹配就可以像下图这样做,这也是 KMP 算法的核心。


看懂了么?前缀直接滑到了后缀的位置上。


为什么可以这么整呢?


因为在第 1 次的时候已经比较过了,在与主串完全匹配的部分里,模式串第 1 个和第 2 个元素与第 3 个、第 4 个完全一样。


此时主串的比较指针 i 继续从 i = 5 开始比较,模式串的比较指针 j 也不需要从 0 开始直接比较,可以从 j = 2 的位置开始比较。

640.png

你看去掉了很多无意义的匹配和回溯,大大提高了效率。

那么现在的问题成了每次不匹配的时候,找之前已匹配部分中,模式串的前后缀,而且还是最长公共前后缀


也就是碰到某个不匹配的时候,我这个模式串要从最长前缀后滑动到最长后缀的位置(其实就是比较指针 j 从最长前缀移动到最长后缀的位置)。而保存这个位置的数组就是 next 数组。


求 next 数组值


next 数组的求解,一向是老大难问题,而且这玩意不只是在写代码的时候折磨人,大学的考试或者考研考试只要涉及数据结构与算法这门课,简直是必考题。


本来想写一下我之前一直常用的求 next 的方法,后来偶然看了 b 站 up 主正月点灯笼的求法,感觉好像更容易理解一些,再此借鉴过来分享给大家。


在这以模式串 T = ababc 为例。


学校用的书呢,讲 KMP 的时候,大多数数组是从下标为 1,而不是 0 开始,所以为了更方便的讲解,这个例子的讲解我会默认数组是从下标为 1 开始的(如果你习惯从 0 开始,就是数组从 1 开始的结果每个值 -1 即可,下面会讲到)。



(1)写出模式串 T 的各个前缀


(2)对于模式串 T 所有的前缀,找每一个前缀的最长公共前后缀。而且最长公共前后缀要比原始字符要短(如果一样长的话则没有意义,因为我们要的是滑动)。


在这里以 “abab” 这个串为例,这时比较指针指向最后一位的时候,出现不匹配:

640.png


那么对于前 3 位 “aba” 来说,首先找长度为 2 的公共前后缀,最长前缀是 “ab”,最长后缀是 “ba”,显然前缀 ≠ 后缀;再来看长度为 1 的公共前后缀,最长前缀是 “a”,最长后缀也是 “a”,最长前缀 = 最长后缀,所以 “abab” 这个最长公共前后缀的长度 = 1。


正常来说,模式串的滑动就是从最长公共前缀 a 滑倒了最长公共后缀 a 的位置,比较指针 j 从 2 开始重新比较。

640.png

一个看不出啥规律,再来看 “ababc”,同样比较指针指向最后一位的时候,出现不匹配:

640.png

对于前 4 位 "abab" 首先找长度为 3 的公共前后缀 ,最长前缀是 “aba”,最长后缀是 “bab”,二者不相等;再找长度为 2 的,最长前缀是 “ab”,最长后缀是 “ab”,二者相等,所以 “ababc” 这个串的最长公共前后缀的长度 = 2。


所以,模式串的滑动从最长前缀 ab 滑到了最长后缀 ab,比较指针 j 从下标为 3 的位置开始重新比较。

640.png

通过上面这两个图不知道你发现了规律没有:


比较指针 j 的所处的位置 = 最长公共前后缀的长度 + 1。


所以最后模式串 T = ababc 的 next 数组的值为下图:

640.png


至于第 1 个为什么是 0,你可以理解为当第 1 个不匹配的话,它的前面是没有任何元素的,记为 -1,那么他这里的值就是 -1 + 1 = 0。


所以对整个模式串 T 求 next 值就齐活了。

640.png

如果你习惯从 0 开始,就是数组从 1 开始的结果每个值 -1:

640.png

# 代码从下标为 0 开始。
def getNext(T):
    # 后缀匹配指向
    i = 0
    # 前缀匹配指向
    j = -1
    # 初始化 next 数组
    next = [-1] * len(T)
    # 此处 next[0] = -1,所以只需要求剩下的 len(T)-1 个即可
    while i < len(T)-1:
        # j == -1 就是找无可找 or 匹配成功,相同前缀长度增加1
        if j == -1 or T[i] == T[j]:
            i += 1
            j += 1
            next[i] = j
        # 匹配不成功则在前面的子串中继续搜索,直至找不到(即 j== -1 的情况)
        else:
            j = next[j]
    return next

匹配操作实现


那求出了 next 数组,我们就来拆分 KMP 模式串匹配的实现。


在这里主串用 S = abcabcabcabda,模式串用上文中求出的 T = abcabd 为例(示例默认数组从下标为 1 开始)。


640.png


从上图可以看出,第 1 次在 i = 4,j = 4 时出现不匹配,而此时 next 的值为 2。


这就意味着,第 2 次,从模式串下标为 2 的位置和主串的当前位置的元素开始匹配,形式如下图。

640.png


上图发现还是不匹配,此时 next 的值为 1,这就意味着,第 3 次从模式串下标为 1 的位置和主串的当前位置的元素进行匹配,形式如下图。

640.png

然后开始的第 3 次。

640.png

看上图,第 3 次在 i = 6,j = 3 的时候出现不匹配,此时的 next 值为 1,那就意味着第 4 次是从模式串 j = 1 的位置与主串的当前位置进行匹配,形式如下图。

640.png

此时模式串和主串上的元素还是不匹配,此时 next 为 0,当 next 值为 0 时,相当于是模式串的当前元素和主串的下一个元素进行比较,如下图。

640.png


然后有进行了第 5 次,发现匹配成功。


# 代码从下标为 0 开始
def KMP(S, T):
    i = 0
    j = 0
    next = getNext(T)
    while i < len(S) and j < len(T):
        #j == -1 找无可找,从 S[i+1] 开始和 T[0] 匹配 or 当匹配成功时,往下匹配。
        if j == -1 or S[i] == T[j]:
            i += 1
            j += 1
        # 匹配不成功则用 next(j) 找下一次匹配的位置
        else:
            j = next[j]
    # 如果模式串在主串中存在
    if j == len(T):
        return i - j
    else:
        return -1

KMP 的讲解到这就全部结束了,真不容易呀,写了好久好久好久。


我自认为 KMP 全部讲清楚了,看懂了保你不管是初学,或者考试、面试都过过过。


你看,KMP 也没那么难学嘛!


提醒一下:我在图解 next 和 KMP 原理的时候用的是数组从 1 开始,建议大家在草稿纸上用我的思路,手动模拟一下数组从 0 开始的情况。


毕竟我给出的代码,数组是从下标为 0 开始的,我就是想看看你们是不是真的懂了。

640.png


用心良苦第一人了。


关于 KMP 的代码也不是很长,建议大家根据原理写一套自己的 KMP 板子,到时候用的时候直接拿出来套就好了。


还是那句话,能看到这的都是真爱,点赞在看留言么么哒给我刷起来~


我是蛋蛋,我们下次见!

相关文章
|
22天前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
16 0
|
25天前
|
算法
KMP算法
KMP算法
22 0
|
3月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
4月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
106 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
3月前
|
算法
KMP算法
KMP算法
25 0
|
4月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
5月前
|
人工智能 算法 BI
一篇文章讲明白KMP算法(俗称看毛片算法)
一篇文章讲明白KMP算法(俗称看毛片算法)
53 0
|
7天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
4天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。