* 总结

读完本篇可以顺便，把leetcode上28.实现strStr()题目做了。

读完本篇可以顺便把leetcode上28.实现strStr()题目做了。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

**后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串**。

**正确理解什么是前缀什么是后缀很重要。**

**正确理解什么是前缀什么是后缀很重要**!

那么网上清一色都说 “kmp 最长公共前后缀” 又是什么回事呢？

我查了一遍 算法导论 和 算法4里KMP的章节，都没有提到 “最长公共前后缀”这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 准确一些。

我查了一遍 算法导论 和 算法4里KMP的章节，都没有提到 “最长公共前后缀”这个词，也不知道从哪里来了，我理解是用“最长相等前后缀” 更准确一些。

**因为前缀表要求的就是相同前后缀的长度。**

以下我们以前缀表统一减一之后的next数组来做演示。

**以下我们以前缀表统一减一之后的next数组来做演示**。

有了next数组，就可以根据next数组来 匹配文本串s，和模式串t了。

暴力的解法显而易见是O(n * m)，所以**KMP在字符串匹配中极大的提高的搜索的效率。**

为了和[字符串：KMP是时候上场了（一文读懂系列）](https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug)字符串命名统一，方便大家理解，以下文章统称haystack为文本串, needle为模式串。

为了和力扣题目28.实现strStr保持一致，方便大家理解，以下文章统称haystack为文本串, needle为模式串。

都知道使用KMP算法，一定要构造next数组。

}

此时所有逻辑的代码都已经写出来了，本题整体代码如下：

此时所有逻辑的代码都已经写出来了，力扣 28.实现strStr 题目的整体代码如下：

我们介绍了什么是KMP，KMP可以解决什么问题，然后分析KMP算法里的next数组，知道了next数组就是前缀表，再分析为什么要是前缀表而不是什么其他表。

接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不同意减一得到的next数组仅仅是kmp的实现方式的不同。

接着从给出的模式串中，我们一步一步的推导出了前缀表，得出前缀表无论是统一减一还是不减一得到的next数组仅仅是kmp的实现方式的不同。

其中还分析了KMP算法的时间复杂度，并且和暴力方法做了对比。

* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)

* B站视频：[代码随想录](https://space.bilibili.com/525438321)

* 知识星球：[代码随想录](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ)

<divalign="center"><imgsrc=../pics/公众号.pngwidth=450alt=> </img></div>

<divalign="center"><imgsrc=../pics/公众号.pngwidth=450alt=> </img></div>

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。

pop() -- 从队列首部移除元素。

peek() -- 返回队列首部的元素。

empty() -- 返回队列是否为空。

push(x) -- 将一个元素放入队列的尾部。

pop() -- 从队列首部移除元素。

peek() -- 返回队列首部的元素。

empty() -- 返回队列是否为空。

示例:

下面动画模拟以下队列的执行过程如下：

执行语句：

queue.push(1);

queue.push(2);

queue.pop();**注意此时的输出栈的操作**

queue.push(3);

queue.push(4);

queue.pop();

queue.pop();**注意此时的输出栈的操作**

queue.pop();

queue.empty();

执行语句：

queue.push(1);

queue.push(2);

queue.pop();**注意此时的输出栈的操作**

queue.push(3);

queue.push(4);

queue.pop();

queue.pop();**注意此时的输出栈的操作**

queue.pop();

queue.empty();



在push数据的时候，只要数据放进输入栈就好，**但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入）**，再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

拿示例一A =[1,4,2], B =[1,2,4]为例，相交情况如图：


其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）