大家好伐,我是侬们的帅蛋。
今天来学能让小儿止啼的 KMP,是不是很慌?
本来在本蛋的计划里,KMP 的顺序还是要往后放一下,但是架不住小婊贝催问。
那还说啥,直接安排!就今天,直奔字符串模式匹配!
你们的需求就是我肝的方向!上面的小老弟留言一次哪成,看着不像铁蛋粉
这次保证安排的明明白白的,文章除了理解 KMP 算法的本质,拿去应付考试题也保证妥妥的!
字符串模式匹配是字符串中最重要的操作之一,就是找模式串在主串中的位置。
臭宝:呃,啥是主串,啥是模式串咧?
蛋蛋:如果你要找字符串 B 在字符串 A 中的位置,那么字符串 A 就是主串,字符串 B 就是模式串。可以理解主串就是大串,模式串就是小串。
字符串模式匹配算法有很多,但是要说提起字符串匹配,大家脑阔里的第一反应还是看毛片,呃,KMP 算法。
KMP 算法匹配字符串非常高效,但是原理有些复杂,学起来脑瓜子嗡嗡的,是学生时代学数据结构与算法绕不过去的坎儿。
不过不慌,这玩意本帅蛋门儿清。掏出你的卫生纸,呃,草稿纸,整活。
要学 KMP 模式匹配算法,首先先明白之前的匹配有多笨,所以我们先来看无脑流暴力匹配。
暴力模式匹配
暴力模式匹配,无脑流的典型代表,没办法情况下的无冕之王。
假设主串的长度为 n,模式串的长度为 m,暴力模式匹配就是对主串的下标为 0 1 2 3 ... n - m 的元素作为模式串的开头,与模式串依次进行匹配,看有没有与模式串完全匹配的。
下面来看一个例子。
从上图可以看出,暴力匹配是在主串的长度下做模式串次匹配。
最好的情况就是从第 1 次开始就匹配成功,此时的时间复杂度就是 O(1)。
最坏情况的情况是,模式串每次都匹配到最后一个才发现和主串不同。比如主串是“aaaaab”,模式串是“aab”。
看上图,除了最后一次,其余的都是每次匹配到最后,才发现,啊,我们不一样。
这种情况下,上图中,模式串在前 3 次,每次都要匹配 3 次,并且不匹配,直到第 4 次,全部匹配,不需要继续移动,所以匹配的次数为(6 - 3 + 1)* 3 = 12 次。
由此可知,对于主串长度为 n,模式串长度为 m ,最坏情况下的时间复杂度为 O((n - m + 1) * m) = O(n * m)。
你看,暴力模式匹配这么低效,你能忍的了?
忍不了吧,来,看毛片!
KMP 模式匹配
KMP 算法全称Knuth Morris Pratt,是由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 三位大佬一起捣鼓出来的。
KMP 算法目的是为了快速的从主串中找到模式串,强调的是快,那咋快的呢?
那肯定是去掉暴力模式匹配中的”无脑“的部分。
上图是暴力模式匹配的前 2 步,有比较指针 i 和 j。
可以看到,在第 1 次匹配的时候,比较指针 i 和 j 走到了下标为 5 的位置发现不匹配的元素,然后进行第 2 次匹配,此时 i 回到了下标为 1 的位置。
如果继续匹配下去的话,你会发现比较指针 i 在频繁的来回折返跑,就像上图第 1 次匹配的时候 i 已经走到了 5,等到了第 2 次匹配的时候 i 又回到了 1。
这种动作叫做回溯,而造成暴力模式匹配效率低下的主要坏蛋就是频繁的比较指针回溯。
KMP 算法做到的就是比较指针不回溯,仅仅是后移模式串。
我们接下来看,这具体是怎么实现的。下面这部分要慢一点,好好体会。
还是以主串 S = abcabcabda,模式串 T = abcabd 为例。
上图是模式串与主串的第一次匹配,在 i = 5,j = 5 的时候出现不匹配的元素,在此之前的元素都是匹配的。
观察一下模式串,你会发现在匹配的部分里,存在相同前后缀的部分。
那第二步的匹配就可以像下图这样做,这也是 KMP 算法的核心。
看懂了么?前缀直接滑到了后缀的位置上。
为什么可以这么整呢?
因为在第 1 次的时候已经比较过了,在与主串完全匹配的部分里,模式串第 1 个和第 2 个元素与第 3 个、第 4 个完全一样。
此时主串的比较指针 i 继续从 i = 5 开始比较,模式串的比较指针 j 也不需要从 0 开始直接比较,可以从 j = 2 的位置开始比较。
你看去掉了很多无意义的匹配和回溯,大大提高了效率。
那么现在的问题成了每次不匹配的时候,找之前已匹配部分中,模式串的前后缀,而且还是最长公共前后缀。
也就是碰到某个不匹配的时候,我这个模式串要从最长前缀后滑动到最长后缀的位置(其实就是比较指针 j 从最长前缀移动到最长后缀的位置)。而保存这个位置的数组就是 next 数组。
求 next 数组值
next 数组的求解,一向是老大难问题,而且这玩意不只是在写代码的时候折磨人,大学的考试或者考研考试只要涉及数据结构与算法这门课,简直是必考题。
本来想写一下我之前一直常用的求 next 的方法,后来偶然看了 b 站 up 主正月点灯笼的求法,感觉好像更容易理解一些,再此借鉴过来分享给大家。
在这以模式串 T = ababc 为例。
学校用的书呢,讲 KMP 的时候,大多数数组是从下标为 1,而不是 0 开始,所以为了更方便的讲解,这个例子的讲解我会默认数组是从下标为 1 开始的(如果你习惯从 0 开始,就是数组从 1 开始的结果每个值 -1 即可,下面会讲到)。
(1)写出模式串 T 的各个前缀
(2)对于模式串 T 所有的前缀,找每一个前缀的最长公共前后缀。而且最长公共前后缀要比原始字符要短(如果一样长的话则没有意义,因为我们要的是滑动)。
在这里以 “abab” 这个串为例,这时比较指针指向最后一位的时候,出现不匹配:
那么对于前 3 位 “aba” 来说,首先找长度为 2 的公共前后缀,最长前缀是 “ab”,最长后缀是 “ba”,显然前缀 ≠ 后缀;再来看长度为 1 的公共前后缀,最长前缀是 “a”,最长后缀也是 “a”,最长前缀 = 最长后缀,所以 “abab” 这个最长公共前后缀的长度 = 1。
正常来说,模式串的滑动就是从最长公共前缀 a 滑倒了最长公共后缀 a 的位置,比较指针 j 从 2 开始重新比较。
一个看不出啥规律,再来看 “ababc”,同样比较指针指向最后一位的时候,出现不匹配:
对于前 4 位 "abab" 首先找长度为 3 的公共前后缀 ,最长前缀是 “aba”,最长后缀是 “bab”,二者不相等;再找长度为 2 的,最长前缀是 “ab”,最长后缀是 “ab”,二者相等,所以 “ababc” 这个串的最长公共前后缀的长度 = 2。
所以,模式串的滑动从最长前缀 ab 滑到了最长后缀 ab,比较指针 j 从下标为 3 的位置开始重新比较。
通过上面这两个图不知道你发现了规律没有:
比较指针 j 的所处的位置 = 最长公共前后缀的长度 + 1。
所以最后模式串 T = ababc 的 next 数组的值为下图:
至于第 1 个为什么是 0,你可以理解为当第 1 个不匹配的话,它的前面是没有任何元素的,记为 -1,那么他这里的值就是 -1 + 1 = 0。
所以对整个模式串 T 求 next 值就齐活了。
如果你习惯从 0 开始,就是数组从 1 开始的结果每个值 -1:
# 代码从下标为 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 开始)。
从上图可以看出,第 1 次在 i = 4,j = 4 时出现不匹配,而此时 next 的值为 2。
这就意味着,第 2 次,从模式串下标为 2 的位置和主串的当前位置的元素开始匹配,形式如下图。
上图发现还是不匹配,此时 next 的值为 1,这就意味着,第 3 次从模式串下标为 1 的位置和主串的当前位置的元素进行匹配,形式如下图。
然后开始的第 3 次。
看上图,第 3 次在 i = 6,j = 3 的时候出现不匹配,此时的 next 值为 1,那就意味着第 4 次是从模式串 j = 1 的位置与主串的当前位置进行匹配,形式如下图。
此时模式串和主串上的元素还是不匹配,此时 next 为 0,当 next 值为 0 时,相当于是模式串的当前元素和主串的下一个元素进行比较,如下图。
然后有进行了第 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 开始的,我就是想看看你们是不是真的懂了。
用心良苦第一人了。
关于 KMP 的代码也不是很长,建议大家根据原理写一套自己的 KMP 板子,到时候用的时候直接拿出来套就好了。
还是那句话,能看到这的都是真爱,点赞在看留言么么哒给我刷起来~
我是蛋蛋,我们下次见!