先学习一下前置知识：帮你把KMP算法学个通透！
思想：当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
思路：next数组就是一个前缀表。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
28. 实现 strStr()
文字讲解：实现strStr()
视频讲解：帮你把KMP算法学个通透！
题设：给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
难点：KMP算法的整体掌握。
public int strStr(String haystack, String needle) {
int m = needle.length();
// 当 needle 是空字符串时我们应当返回 0
if (m == 0) {
return 0;
}
int n = haystack.length();
if (n < m) {
return -1;
}
int i = 0;
int j = 0;
while (i < n - m + 1) {
// 找到首字母相等
while (i < n && haystack.charAt(i) != needle.charAt(j)) {
i++;
}
if (i == n) {// 没有首字母相等的
return -1;
}
// 遍历后续字符，判断是否相等
i++;
j++;
while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
if (j == m) {// 找到
return i - j;
} else {// 未找到
i -= j - 1;
j = 0;
}
}
return -1;
}
易错点：KMP算法的各种细节。
复杂度分析：
- 时间复杂度: O(n + m)
- 空间复杂度: O(m)
459.重复的子字符串
文字讲解：重复的子字符串
视频讲解：字符串这么玩，可有点难度！
