KMP算法理论基础

KMP算法是一种高效的字符串搜索算法，用于在一个较大的文本串中查找一个给定的模式串。 KMP算法的关键思想是通过利用先前匹配的信息来避免不必要的字符比较。它对模式串进行预处理，构建一个“next表”，这有助于确定在出现不匹配时从哪里继续匹配。

next数组的原理与代码实现：

原理以例子说明

文本串：aabaabaafa  模式串：aabaaf

1. 前缀：包含首字母（从首字母开始），且不包含末字母的所有子串。

    后缀：不包含首字母，且包含末字母（结尾在末字母）的所有子串。

2. next 数组的本质就是"以当前字母为结尾的字符串"的“最长相等前后缀”的长度。模式串：aabaaf 的next = [0, 1, 0, 1, 2, 0]

代码实现

定义两个变量 i, j。这里 j 是前缀的末尾，因此初始化为0；i 为后缀的末尾，初始化为1(因为长度为1的字符串没有前后缀，至少长度为2).

i 定位字符串末尾的位置。j 定位前缀末尾的位置（也就是最长相等前后缀的长度）。

当匹配时：最长相等前后缀长度 j 加一。更新next数组。

当不匹配时：比如前缀‘aab'和后缀‘aaf’ 前两位都配上了，但到'f'不匹配，此时 i = 5, j = 2。不匹配就找前一位的next数组的值 next[j-1] = 1, 代表j应该跳回到1, pattern[5]与pattern[1]还是不等。那就继续回退到j=0.

KMP算法的原理与代码实现：

文本串：aabaabaafa  模式串：aabaaf。next数组算出来为[0, 1, 0, 1, 2, 0]

变量 i, j：i 为文本串的当前位置，j 为模式串的当前位置。

当匹配时：匹配长度加一，然后继续看下一位 i,j 是否能接着配上。

当不匹配时：比如‘aabaa’都配上了，但到'f'不匹配，此时 j = 5, 应该看next数组的前一位Next[5-1] = 2，代表我们应该跳回到2。因为后缀aa与前缀aa一样，既然后缀aa的下一位配不上，就退回去看前缀的后一位能否配上。( 2 是前缀的长度，也是前缀后一位字符的index。)

28. 实现 strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

思路：KMP算法的一个简单应用，前面已经详述，这里就不赘述了。

459.重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

思路：暴力解法就不做了，反正我也不会。这道题算是next数组的妙用。

比如'abcabcabc'对应的next数组为[0,0,0,1,2,3,4,5,6]。重复子串为‘abc’前三位next数组都为0。后面因为都是重复的，next数组值自增1。因此，字符串长度 - next数组的末位数即重复子串的长度。

那判断条件就是：1. 重复子串长度不能超过字符串的一半。2. 字符串的长度恰好是重复子串长度的倍数。

以下是卡哥资料

28. 实现 strStr()  （本题可以跳过）

因为KMP算法很难，大家别奢求 一次就把kmp全理解了，大家刚学KMP一定会有各种各样的疑问，先留着，别期望立刻啃明白，第一遍了解大概思路，二刷的时候，再看KMP会 好懂很多。

或者说大家可以放弃一刷可以不看KMP，今天来回顾一下之前的算法题目就可以。

因为大家 算法能力还没到，细扣 很难的算法，会把自己绕进去，就算别人给解释，只会激发出更多的问题和疑惑。所以大家先了解大体过程，知道这么回事， 等自己有 算法基础和思维了，在看多看几遍视频，慢慢就理解了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html

 459.重复的子字符串  （本题可以跳过）

本题算是KMP算法的一个应用，不过 对KMP了解不够熟练的话，理解本题就难很多。 

我的建议是 KMP和本题，一刷的时候 ，可以适当放过，了解怎么回事就行，二刷的时候再来硬啃

题目链接/文章讲解/视频讲解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

字符串总结 

比较简单，大家读一遍就行 

题目链接/文章讲解：https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html

 双指针回顾 

此时我们已经做过10到双指针的题目了，来一起回顾一下，大家自己也总结一下双指针的心得 

文章讲解：https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html