一、什么是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其实就是前缀表。
三、重要题型:
匹配问题:
重复子串问题: