前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两天晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
链表的合集
字符串
实现 strStr()
给你两个字符串 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 。
思路
一看这题就是知道是经典的字符串匹配的题,那肯定第一个就肯定可以用暴力匹配的嘛，我们来看看暴力匹配的写法
暴力解法
class Solution { public int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); for (int i = 0; i + m <= n; i++) { boolean flag = true; for (int j = 0; j < m; j++) { if (haystack.charAt(i + j) != needle.charAt(j)) { flag = false; break; } } if (flag) { return i; } } return -1; } }
Knuth-Morris-Pratt 算法
什么是KMP
说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。
因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP
KMP有什么用
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
其实KMP的代码不好理解，一些同学甚至直接把KMP代码的模板背下来。
没有彻底搞懂，懵懵懂懂就把代码背下来太容易忘了。
不仅面试的时候可能写不出来，如果面试官问：next数组里的数字表示的是什么，为什么这么表示？
估计大多数候选人都是懵逼的。
什么是前缀表
写过KMP的同学，一定都写过next数组，那么这个next数组究竟是个啥呢？
next数组就是一个前缀表（prefix table）。
前缀表有什么作用呢？
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
为了清楚的了解前缀表的来历，我们来举一个例子：
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
请记住文本串和模式串的作用，对于理解下文很重要，要不然容易看懵。所以说三遍：
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
代码
class Solution { public int strStr(String haystack, String needle) { int n = haystack.length(), m = needle.length(); if (m == 0) { return 0; } int[] pi = new int[m]; for (int i = 1, j = 0; i < m; i++) { while (j > 0 && needle.charAt(i) != needle.charAt(j)) { j = pi[j - 1]; } if (needle.charAt(i) == needle.charAt(j)) { j++; } pi[i] = j; } for (int i = 0, j = 0; i < n; i++) { while (j > 0 && haystack.charAt(i) != needle.charAt(j)) { j = pi[j - 1]; } if (haystack.charAt(i) == needle.charAt(j)) { j++; } if (j == m) { return i - m + 1; } } return -1; } }
结束
kmp还是有点难度的，大家要多理解，多做，慢慢就会了 我是小六六，三天打鱼，两天晒网！
