@@ -29,9 +29,178 @@ https://leetcode-cn.com/problems/implement-strstr/
2929
3030KMP的经典思想就是:** 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。**
3131
32- 如果对KMP理论基础还不够了解的同学请看 [ 字符串：KMP是时候上场了（一文读懂系列） ] ( https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug ) 。
32+ 本篇将以如下顺序来讲解KMP，
3333
34- ** 为了和[ 字符串：KMP是时候上场了（一文读懂系列）] ( https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug ) 字符串命名统一，方便大家理解，以下文章统称haystack为文本串, needle为模式串。**
34+ 1 . 什么是KMP
35+ 2 . KMP可以解决什么问题
36+ 3 . 分析KMP算法里的next数组
37+ 4 . 什么是前缀表
38+ 5 . 再分析为什么要是前缀表而不是什么哈希表其他表等等，偏偏要是前缀表。
39+ 6 . 一步一步推导前缀表是怎么求的
40+ 7 . 时间复杂度分析
41+ 8 . 前缀表与next数组的关系
42+ 9 . 如何使用next数组来做一遍匹配的过程
43+ 10 . 构造next数组
44+ 11 . 使用next数组进行匹配
45+ 12 . 前缀表统一减一（右移）的KMP实现方式
46+ 13 . 前缀表不减一的KMP实现方式
47+ 14 . 总结
48+
49+ 可以说步步相扣，大家要跟紧，哈哈。
50+
51+ #什么是KMP
52+
53+ 说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。
54+
55+ 因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP
56+
57+ #KMP有什么用
58+
59+ KMP主要应用在字符串匹配上。
60+
61+ KMP的主要思想是** 当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。**
62+
63+ 所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
64+
65+ 其实KMP的代码不好理解，一些同学甚至直接把KMP代码的模板背下来。
66+
67+ 没有彻底搞懂，懵懵懂懂就把代码背下来太容易忘了。
68+
69+ 不仅面试的时候可能写不出来，如果面试官问：** next数组里的数字表示的是什么，为什么这么表示？**
70+
71+ 估计大多数候选人都是懵逼的。
72+
73+ 下面Carl就带大家把KMP的精髓，next数组弄清楚。
74+
75+ #什么是前缀表
76+
77+ 写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？
78+
79+ next数组就是一个前缀表（prefix table）。
80+
81+ 前缀表有什么作用呢？
82+
83+ ** 前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。**
84+
85+ 为了清楚的了解前缀表的来历，我们来举一个例子：
86+
87+ 要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
88+
89+ 请记住文本串和模式串的作用，对于理解下文很重要，要不然容易看懵。所以说三遍：
90+
91+ 要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
92+
93+ 要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
94+
95+ 要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
96+
97+ 如动画所示：
98+
99+ <img src =' ../../media/video/KMP精讲1.gif ' width =600 > </img ></div >
100+
101+ 动画里，我特意把 子串` aa ` 标记上了，这是有原因的，大家先注意一下，后面还会说道。
102+
103+ 可以看出，文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，会发现不匹配，此时就要从头匹配了。
104+
105+ 但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。
106+
107+ 此时就要问了** 前缀表是如何记录的呢？**
108+
109+ 首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，在重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。
110+
111+ 那么什么是前缀表：** 记录下表i之前（包括i）的字符串中，有多大长度的相同前缀后缀。**
112+
113+ #为什么一定要用前缀表
114+
115+ 这就是前缀表那为啥就能告诉我们 上次匹配的位置，并跳过去呢？
116+
117+ 回顾一下，刚刚匹配的过程在下表5的地方遇到不匹配，模式串是指向f，如图：
118+ <img src =' ../../media/pics/KMP精讲1.png ' width =600 > </img ></div >
119+
120+
121+ 然后就找到了下表2，指向b，继续匹配：如图：
122+ <img src =' ../../media/pics/KMP精讲2.png ' width =600 > </img ></div >
123+
124+ 以下这句话，对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要！
125+
126+ ** 下表5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。**
127+
128+ 所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。
129+
130+ ** 很多介绍KMP的文章或者视频并没有把为什么要用前缀表？这个问题说清楚，而是直接默认使用前缀表。**
131+
132+ #如何计算前缀表
133+
134+ 接下来就要说一说怎么计算前缀表。
135+
136+ 如图：
137+
138+ <img src =' ../../media/pics/KMP精讲5.png ' width =600 > </img ></div >
139+
140+ 长度为前1个字符的子串` a ` ，最长相同前后缀的长度为0。（注意字符串的** 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串** ；** 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串** 。）
141+
142+ <img src =' ../../media/pics/KMP精讲6.png ' width =600 > </img ></div >
143+ 长度为前2个字符的子串` aa ` ，最长相同前后缀的长度为1。
144+
145+ <img src =' ../../media/pics/KMP精讲7.png ' width =600 > </img ></div >
146+ 长度为前3个字符的子串` aab ` ，最长相同前后缀的长度为0。
147+
148+ 以此类推：
149+ 长度为前4个字符的子串` aaba ` ，最长相同前后缀的长度为1。
150+ 长度为前5个字符的子串` aabaa ` ，最长相同前后缀的长度为2。
151+ 长度为前6个字符的子串` aabaaf ` ，最长相同前后缀的长度为0。
152+
153+ 那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：
154+ <img src =' ../../media/pics/KMP精讲8.png ' width =600 > </img ></div >
155+
156+ 可以看出模式串与前缀表对应位置的数字表示的就是：** 下表i之前（包括i）的字符串中，有多大长度的相同前缀后缀。**
157+
158+ 再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示：
159+
160+ <img src =' ../../media/video/KMP精讲2.gif ' width =600 > </img ></div >
161+
162+ 找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。
163+
164+ 为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。
165+
166+ 所以要看前一位的 前缀表的数值。
167+
168+ 前一个字符的前缀表的数值是2， 所有把下表移动到下表2的位置继续比配。 可以再反复看一下上面的动画。
169+
170+ 最后就在文本串中找到了和模式串匹配的子串了。
171+
172+ #前缀表与next数组
173+
174+ 很多KMP算法的时间都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？
175+
176+ next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。
177+
178+ 为什么这么做呢，其实也是很多文章视频没有解释清楚的地方。
179+
180+ 其实** 这并不涉及到KMP的原理，而是具体实现，next数组即可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。**
181+
182+ 后面我会提供两种不同的实现代码，大家就明白了了。
183+
184+ #使用next数组来匹配
185+
186+ 以下我们以前缀表统一减一之后的next数组来做演示。
187+
188+ 有了next数组，就可以根据next数组来 匹配文本串s，和模式串t了。
189+
190+ 注意next数组是新前缀表（旧前缀表统一减一了）。
191+
192+ 匹配过程动画如下：
193+
194+ <img src =' ../../media/video/KMP精讲4.gif ' width =600 > </img ></div >
195+
196+ #时间复杂度分析
197+
198+
199+ 其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
200+
201+ 暴力的解法显而易见是O(n * m)，所以** KMP在字符串匹配中极大的提高的搜索的效率。**
202+
203+ 为了和[ 字符串：KMP是时候上场了（一文读懂系列）] ( https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug ) 字符串命名统一，方便大家理解，以下文章统称haystack为文本串, needle为模式串。
35204
36205都知道使用KMP算法，一定要构造next数组。
37206
@@ -62,7 +231,7 @@ int j = -1;
62231next[0] = j;
63232```
64233
65- j 为什么要初始化为 -1呢，因为之前说过前缀表要统一减一的操作，所以j初始化为-1 。
234+ j 为什么要初始化为 -1呢，因为之前说过前缀表要统一减一的操作仅仅是其中的一种实现，我们这里选择j初始化为-1，下文我还会给出j不初始化为-1的实现代码 。
66235
67236next[ i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）
68237
@@ -200,7 +369,7 @@ for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
200369
201370此时所有逻辑的代码都已经写出来了，本题整体代码如下：
202371
203- ## C++代码
372+ #前缀表统一减一 C++代码实现
204373
205374```
206375class Solution {
@@ -242,7 +411,61 @@ public:
242411
243412```
244413
245- 前缀表不减一版本
414+ #前缀表（不减一）C++实现
415+
416+ 那么前缀表就不减一了，也不右移的，到底行不行呢？行！
417+
418+ 我之前说过，这仅仅是KMP算法实现上的问题，如果就直接使用前缀表可以换一种回退方式，找j=next[ j-1] 来进行回退。
419+
420+ 主要就是j=next[ x] 这一步最为关键！
421+
422+ 我给出的getNext的实现为：（前缀表统一减一）
423+
424+ ```
425+ void getNext(int* next, const string& s) {
426+ int j = -1;
427+ next[0] = j;
428+ for(int i = 1; i < s.size(); i++) { // 注意i从1开始
429+ while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
430+ j = next[j]; // 向前回溯
431+ }
432+ if (s[i] == s[j + 1]) { // 找到相同的前后缀
433+ j++;
434+ }
435+ next[i] = j; // 将j（前缀的长度）赋给next[i]
436+ }
437+ }
438+
439+ ```
440+ 此时如果输入的模式串为aabaaf，对应的next为-1 0 -1 0 1 -1。
441+
442+ 这里j和next[ 0] 初始化为-1，整个next数组是以 前缀表减一之后的效果来构建的。
443+
444+ 那么前缀表不减一来构建next数组，代码如下：
445+
446+ ```
447+ void getNext(int* next, const string& s) {
448+ int j = 0;
449+ next[0] = 0;
450+ for(int i = 1; i < s.size(); i++) {
451+ while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下表的操作
452+ j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
453+ }
454+ if (s[i] == s[j]) {
455+ j++;
456+ }
457+ next[i] = j;
458+ }
459+ }
460+
461+ ```
462+
463+ 此时如果输入的模式串为aabaaf，对应的next为 0 1 0 1 2 0，（其实这就是前缀表的数值了）。
464+
465+ 那么用这样的next数组也可以用来做匹配，代码要有所改动。
466+
467+ 实现代码如下：
468+
246469```
247470class Solution {
248471public:
@@ -281,5 +504,21 @@ public:
281504 }
282505};
283506```
507+
508+ #总结
509+
510+ 我们介绍了什么是KMP，KMP可以解决什么问题，然后分析KMP算法里的next数组，知道了next数组就是前缀表，再分析为什么要是前缀表而不是什么其他表。
511+
512+ 接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不同意减一得到的next数组仅仅是kmp的实现方式的不同。
513+
514+ 其中还分析了KMP算法的时间复杂度，并且和暴力方法做了对比。
515+
516+ 然后先用前缀表统一减一得到的next数组，求得文本串s里是否出现过模式串t，并给出了具体分析代码。
517+
518+ 又给出了直接用前缀表作为next数组，来做匹配的实现代码。
519+
520+ 可以说把KMP的每一个细微的细节都扣了出来，毫无遮掩的展示给大家了！
521+
522+
284523> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
285524