在之前刷力扣的过程中，我每刷道题都是先看题解然后再去边写边看，很多内容根本没消化，在进度上欺骗自己，感觉之前刷的都忘了，能力没有什么提升，现在还是一道都不会做。所以这次报了卡哥的算法训练营，希望能够按计划地有效刷题。本次刷题，我用的是 Java 语言解题，有余力的话也可能会加上 C++ 的题解。以下是算法训练营第九天的刷题记录和思考笔记。
一、KMP 算法
Knuth-Morris-Pratt 算法，简称 KMP 算法，由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三人于 1977 年联合发表，主要应用在字符串匹配上。
KMP 算法的核心为前缀函数，记作 $π(i)$，其定义如下：对于长度为 m 的字符串 s，其前缀函数 $π(i)（0≤i<m）$ 表示 s 的子串 $s[0:i]$ 的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么 $π(i)=0$。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。例如，字符串 aabaaab 的前缀函数值依次为 0, 1, 0, 1, 2, 2, 3。
一刷先不看 KMP，留空等二刷补
28.实现 strStr()
459.重复的子字符串
四、字符串和双指针总结
双指针法在数组，链表和字符串中很常用。
原地移除数组上的元素，由于数组上的元素不能真正的删除，只能覆盖，双指针法通过两个指针在一个 for 循环下完成两个 for 循环的工作。
其实很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。在删除冗余空格的过程中，如果不注意代码效率，很容易写成了 O(n^2) 的时间复杂度。其实使用双指针法 O(n) 就可以搞定。
使用双指针法来翻转链表，只需要改变链表的 next 指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。