代码随想录算法训练营第9天 | 字符串总结 + 双指针回顾+初识KMP算法

28. 实现 strStr(): 找出字符串中第一个匹配项的下标 - Medium

题目链接：. - 力扣（LeetCode）

??? 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回? -1 。

??? 示例 1：

??? 输入：haystack = "sadbutsad", needle = "sad"
??? 输出：0
??? 解释："sad" 在下标 0 和 6 处匹配。
??? 第一个匹配项的下标是 0 ，所以返回 0 。
??? 示例 2：

??? 输入：haystack = "leetcode", needle = "leeto"
??? 输出：-1
??? 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

一刷大致知道KMP算法理论，对处理题上无从下手，二刷再回看

459.重复的子字符串 - Easy

题目链接：. - 力扣（LeetCode）

??? 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

??? 示例 1:

??? 输入: s = "abab"
??? 输出: true
??? 解释: 可由子串 "ab" 重复两次构成。
??? 示例 2:

??? 输入: s = "aba"
??? 输出: false
??? 示例 3:

??? 输入: s = "abcabcabcabc"
??? 输出: true
??? 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

?同上，一刷暂且跳过

字符串总结

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组

打基础的时候，不要太迷恋于库函数

• 如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数
• 如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章?

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了?

• KMP的精髓所在就是前缀表（前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。）
• 针对前缀表到底要不要减一，这其实是不同KMP实现的方式，其中主要理解j=next[x]这一步最为关键！

双指针法是字符串处理的常客

双指针回顾?

数组篇

原地移除数组上的元素，通过两个指针在一个for循环下完成两个for循环的工作

字符串篇

• 反转字符串，使用双指针法，定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素
• 在替换空格?(opens new window) 中使用双指针填充字符串的方法，首先扩充数组到每个空格替换成"%20"之后的大小。然后双指针从后向前替换空格
• 在字符串：花式反转还不够！中，使用双指针法，用O(n)的时间复杂度完成字符串删除类的操作，因为题目要删除冗余空格。在删除冗余空格的过程中，如果不注意代码效率，很容易写成了O(n^2)的时间复杂度。其实使用双指针法O(n)就可以搞定

链表篇

• 使用双指针法来翻转链表，只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表
• 在链表中求环，使用快慢指针（双指针法），分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环

N数之和篇?

三数之和，使用双指针法通过前后两个指针不算向中间逼近，在一个for循环下完成两个for循环的工作，四数之和，其实思路是一样的，在三数之和的基础上再套一层for循环，依然是使用双指针法

今日总结

学习了KMP算法的理论知识，回看总结了双指针法和字符串