首先，利用上一节的结论。既然是在 P[5] 失配的，那么说明 S[0:5] 等于 P[0:5]，即"abcab". 现在我们来考虑：从 S[1]、S[2]、S[3] 开始的匹配尝试，有没有可能成功？
从 S[1] 开始肯定没办法成功，因为 S[1] = P[1] = ‘b’，和 P[0] 并不相等。从 S[2] 开始也是没戏的，因为 S[2] = P[2] = ‘c’，并不等于P[0]. 但是从 S[3] 开始是有可能成功的——至少按照已知的信息，我们推不出矛盾。

带着“跳过不可能成功的尝试”的思想，我们来看next数组。

next数组

next数组是对于模式串而言的。P 的 next 数组定义为：next[i] 表示 P[0] ~ P[i] 这一个子串，使得 前k个字符恰等于后k个字符 的最大的k. 特别地，k不能取i+1（因为这个子串一共才 i+1 个字符，自己肯定与自己相等，就没有意义了）。

上图给出了一个例子。P=“abcabd"时，next[4]=2，这是因为P[0] ~ P[4] 这个子串是"abcab”，前两个字符与后两个字符相等，因此next[4]取2. 而next[5]=0，是因为"abcabd"找不到前缀与后缀相同，因此只能取0.

如果把模式串视为一把标尺，在主串上移动，那么 Brute-Force 就是每次失配之后只右移一位；改进算法则是每次失配之后，移很多位，跳过那些不可能匹配成功的位置。但是该如何确定要移多少位呢？

在 S[0] 尝试匹配，失配于 S[3] <=> P[3] 之后，我们直接把模式串往右移了两位，让 S[3] 对准 P[1]. 接着继续匹配，失配于 S[8] <=> P[6], 接下来我们把 P 往右平移了三位，把 S[8] 对准 P[3]. 此后继续匹配直到成功。
我们应该如何移动这把标尺？很明显，如图中蓝色箭头所示，旧的后缀要与新的前缀一致（如果不一致，那就肯定没法匹配上了）！

回忆next数组的性质：P[0] 到 P[i] 这一段子串中，前next[i]个字符与后next[i]个字符一模一样。既然如此，如果失配在 P[r], 那么P[0]~P[r-1]这一段里面，前next[r-1]个字符恰好和后next[r-1]个字符相等——也就是说，我们可以拿长度为 next[r-1] 的那一段前缀，来顶替当前后缀的位置，让匹配继续下去！
您可以验证一下上面的匹配例子：P[3]失配后，把P[next[3-1]]也就是P[1]对准了主串刚刚失配的那一位；P[6]失配后，把P[next[6-1]]也就是P[3]对准了主串刚刚失配的那一位。

如上图所示，绿色部分是成功匹配，失配于红色部分。深绿色手绘线条标出了相等的前缀和后缀，其长度为next[右端]. 由于手绘线条部分的字符是一样的，所以直接把前面那条移到后面那条的位置。因此说，next数组为我们如何移动标尺提供了依据。接下来，我们实现这个优化的算法。

利用next数组进行匹配

了解了利用next数组加速字符串匹配的原理，我们接下来代码实现之。分为两个部分：建立next数组、利用next数组进行匹配。
首先是建立next数组。我们暂且用最朴素的做法，以后再回来优化：

如上图代码所示，直接根据next数组的定义来建立next数组。不难发现它的复杂度是

的。
接下来，实现利用next数组加速字符串匹配。代码如下：

如何分析这个字符串匹配的复杂度呢？乍一看，pos值可能不停地变成next[pos-1]，代价会很高；但我们使用摊还分析，显然pos值一共顶多自增len(S)次，因此pos值减少的次数不会高于len(S)次。由此，复杂度是可以接受的，不难分析出整个匹配算法的时间复杂度：O(n+m).

快速求next数组

终于来到了我们最后一个问题——如何快速构建next数组。
首先说一句：快速构建next数组，是KMP算法的精髓所在，核心思想是“P自己与自己做匹配”。
为什么这样说呢？回顾next数组的完整定义：

• 定义 “k-前缀” 为一个字符串的前 k 个字符； “k-后缀” 为一个字符串的后 k 个字符。k 必须小于字符串长度。
• next[x] 定义为： P[0]~P[x] 这一段字符串，使得k-前缀恰等于k-后缀的最大的k.

这个定义中，不知不觉地就包含了一个匹配——前缀和后缀相等。接下来，我们考虑采用递推的方式求出next数组。如果next[0], next[1], … next[x-1]均已知，那么如何求出 next[x] 呢？

来分情况讨论。首先，已经知道了 next[x-1]（以下记为now），如果 P[x] 与 P[now] 一样，那最长相等前后缀的长度就可以扩展一位，很明显 next[x] = now + 1. 图示如下。

刚刚解决了 P[x] = P[now] 的情况。那如果 P[x] 与 P[now] 不一样，又该怎么办？

如图。长度为 now 的子串 A 和子串 B 是 P[0]~P[x-1] 中最长的公共前后缀。可惜 A 右边的字符和 B 右边的那个字符不相等，next[x]不能改成 now+1 了。因此，我们应该缩短这个now，把它改成小一点的值，再来试试 P[x] 是否等于 P[now].
now该缩小到多少呢？显然，我们不想让now缩小太多。因此我们决定，在保持“P[0]~P[x-1]的now-前缀仍然等于now-后缀”的前提下，让这个新的now尽可能大一点。 P[0]~P[x-1] 的公共前后缀，前缀一定落在串A里面、后缀一定落在串B里面。换句话讲：接下来now应该改成：使得 A的k-前缀等于B的k-后缀 的最大的k.
您应该已经注意到了一个非常强的性质——串A和串B是相同的！B的后缀等于A的后缀！因此，使得A的k-前缀等于B的k-后缀的最大的k，其实就是串A的最长公共前后缀的长度 —— next[now-1]！

来看上面的例子。当P[now]与P[x]不相等的时候，我们需要缩小now——把now变成next[now-1]，直到P[now]=P[x]为止。P[now]=P[x]时，就可以直接向右扩展了。

代码实现如下：

应用摊还分析，不难证明构建next数组的时间复杂度是O(m)的。至此，我们以O(n+m)的时间复杂度，实现了构建next数组、利用next数组进行字符串匹配。

以上就是KMP算法。它于1977年被提出，全称 Knuth–Morris–Pratt 算法。让我们记住前辈们的名字：Donald Knuth(K), James H. Morris(M), Vaughan Pratt§.
希望本文对你有帮助。 本文在我博客的url是 https://ruanx.pw/kmp/ , 以后可能会更新。

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数初中级安卓工程师，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Android移动开发全套学习资料》送给大家，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频
如果你觉得这些内容对你有帮助，可以添加下面V无偿领取！（备注Android）

最后说一下我的学习路线

其实很简单就下面这张图，含概了Android所有需要学的知识点，一共8大板块：

1. 架构师筑基必备技能
2. Android框架体系架构（高级UI+FrameWork源码）
3. 360°Androidapp全方位性能调优
4. 设计思想解读开源框架
5. NDK模块开发
6. 移动架构师专题项目实战环节
7. 移动架构师不可不学习微信小程序
8. 混合开发的flutter

Android学习的资料

我呢，把上面八大板块的分支都系统的做了一份学习系统的资料和视频，大概就下面这些，我就不全部写出来了，不然太长了影响大家的阅读。需要的小伙伴可以私信我【进阶】我免费分享给大家，或者直接点击下面链接领取，谢谢大家这么久以来的支持。

Android学习PDF+架构视频+面试文档+源码笔记

如果你有其他需要的话，也可以在GitHub上查看，下面的资料也会陆续上传到Github

330页PDF Android学习核心笔记（内含上面8大板块）

Android学习的系统对应视频

总结

我希望通过我自己的学习方法来帮助大家去提升技术：

• 1、多看书、看源码和做项目，平时多种总结

• 2、不能停留在一些基本api的使用上，应该往更深层次的方向去研究，比如activity、view的内部运行机制，比如Android内存优化，比如aidl，比如JNI等，并不仅仅停留在会用，而要通过阅读源码，理解其实现原理

• 3、同时对架构是有一定要求的，架构是抽象的，但是设计模式是具体的，所以一定要加强下设计模式的学习

• 4、android的方向也很多，高级UI，移动架构师，数据结构与算法和音视频FFMpeg解码，如果你对其中一项比较感兴趣，就大胆的进阶吧！

  进阶学习资料领取方式：GitHub

• 4、android的方向也很多，高级UI，移动架构师，数据结构与算法和音视频FFMpeg解码，如果你对其中一项比较感兴趣，就大胆的进阶吧！

  进阶学习资料领取方式：GitHub

希望大家多多点赞，转发，评论加关注，你们的支持就是我继续下去的动力！加油！