【leetcode】刷题，KMP算法学习【学习笔记+代码实现】

KMP算法具体内容：

1.前后缀：前缀/不包含最后一个元素之外的所有子字符串，后缀/不包含第一个元素之外的所有子字符串。

快速找法：其实可以这么快速的理解，排列组合，前缀就是正向的把当前字符串最后一个元素去掉，然后剩下的元素按顺序排列组合的得到的几种可能；后缀就是反向（也就是从右向左）的把当前字符串第一个元素去掉，然后剩下的元素按顺序排列组合的得到的几种可能。

2.最长相等前后缀：是指前后缀中完全相同的元素的最多的个数。

3.前缀表：每个元素作为当前字符串最后一个元素时对应的的最长相等前后缀个数组成的数组。

4.前缀表的作用：这个表真的有点抽象在的，比如为什么要写前缀表？为什么是不匹配元素的前一个元素的最长相等前后缀？对照这张图，最长相等前后缀就是出现对称的位置这个意思，对称就意味着前后相同中间可能有区别，因为我们要对比模式串也就是子串在文本串出现的情况，这种情况下其实是减轻了遍历的复杂程度。这么理解的话就能明白为什么要从不匹配字符的前一位找了。就是一个提高效率的过程。

5.next数组：就是对前缀表做了一点“你乐意”的变换，可以直接用前缀表做next数组，也可以都减一，也可以向右移...但始终不变的一个思路是，你都要找不匹配元素前一个元素对应的最长相等前后缀，细节可以根据自己的习惯来写。

怎么求next数组呢？也就是求前缀表。这是一个找相同元素的问题，双指针可以解决。定义两个指针i和j，j指向前缀终止位置（严格来说是终止位置减一的位置），i指向后缀终止位置（与j同理）。就直接对前缀表都做-1当作next数组方法分析，初始化j=-1，next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j），所以初始化next[0] = j 。

因为j初始化为-1，那么i就从1开始，进行s[i] 与 s[j+1]的比较。然后保持着一个不变的思路，遇见冲突就找前一位，如果s[i]和s[j+1]不相等说明这两个位置就是不匹配，那么就要寻找s[j]的next数组对应值，去s中找这个值对应下标的元素再继续循环遍历。这个过程就是回退，回退到相等或者起点为止。没有冲突的话就i，j都继续往下走。

重点：这里千万别忘了是对一个字符串求next数组，搞错对象就理解错啦。

6.关于写代码我觉得最关键的一步是记好j是从哪里开始的，如果next是前缀表-1，那回退的时候就是不匹配前一个元素对应的next值为索引的模式串再继续和当前位置继续对比。