第四章 KMP算法理论基础

KMP算法理论基础

文章目录

​​KMP算法理论基础​​​​一、什么是KMP​​

​​1.2为何学KMP？​​

​​二、什么是前缀、前缀表​​

​​2.1先认识一下什么是前缀：​​​​2.2认识一下什么是前缀表？​​

​​三、重要题型：​​

一、什么是KMP

KMP代表三个科学家的名字首字母大写。

三位大神分别是：

​​Knuth​​​​Morris​​​​Pratt​​

取了三位学者名字的首字母。所以叫做KMP

1.2为何学KMP？

KMP主要应用在 字符串匹配上。KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

二、什么是前缀、前缀表

前缀和前缀表是KMP里的重要知识点，在主串和模式串进行匹配的时候，当出现不匹配的时候，模式串应该从哪里重新开始匹配，这就是前缀表的作用。

如果没有前缀表，那么就会直接暴力穷举模式串与主串进行匹配。（这种方法效率低，时间复杂度为O(m*n))

2.1先认识一下什么是前缀：

不包含最后一个字符的连续字符串。

2.2认识一下什么是前缀表？

认识前缀表之前需要知道 最长相等前后缀这个概念。因为前缀表就是 模式串的 最长相等前后缀的合集。

所谓最长相等前后缀就是：蓝色套住的那一坨。[先找出中间字符，两头找对称，能对称的字符为一组，不能的为0]

最长相等前后缀的长度本质就是： 对应前缀表的元素：

当模式串出现不匹配的时候，如下图：我们可以查看f上一个元素a的前缀表为 2；那么模式串下一次就从 数组下标为2的模式串的位置开始匹配！

NOTE：

next数组和prefix其实就是前缀表。

三、重要题型：

匹配问题：

​​28.实现strStr()​​

重复子串问题：

​​459.重复的子字符串​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。