字符串系列最后两题，地狱 KMP😭今天先小理解一波~
28. 实现 strStr()
题目描述：
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解题方法：KMP 算法
思考：
KMP中心思想：next数组的构成和比较的过程
KMP算法的核心是判断某个字串是否出现在另一个文本串中，我们通过获得前最表来获取文本串和模式串中
最长相等前后缀长度，保存在next数组中；当文本串和模式串进行比较时，若元素相等，则进位；若元素不相等，
位于模式串的指针要进行回退，回退到next数组前一位标记的位置，也就是上一个最长相等前后缀长度的位置，
再跟文本串进行比较，若字符相等，则从该为后开始继续匹配；若还是不想等，则模式串指针继续回退，直到无法回退；
KMP优点：
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，
可以利用这些信息避免从头再去做匹配了。
该题思路：
1.先获取所给字符串的next数组，并编写getNext函数；
2.根据next数组，获取最长相等前后缀的长度next[len-1]
判断如果 字符串总长度 %（字符串的总长度-最长相等前后缀长度）为0的话，则字符串的总长度是可以被
最长前后缀的长度除尽的，因此整个字符串可以被最长相等前后缀重复组成
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) {
return 0;
}
//创建next数组，并获取needle的next数组
int[] next = new int[needle.length()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {
j = next[j -1];
}
if (needle.charAt(j) == haystack.charAt(i)) {
j++;
}
if (j == needle.length()) {
return i - needle.length() + 1;
}
}
return -1;
}
private void getNext(int[] next, String s) {
int j = 0;
//对于第一个字符，没有前缀也没有后缀，因此前后缀相同部分为0；
next[0] = j;
//j为后缀字串，i为前缀字串，因此初始化i位1，j为0
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i)) {
j = next[j - 1];
//比较i，j所在的字符，如果不相等，j就退回next数组中前一位标记的位置
//因为next数组记录的是前缀后缀相等字符串的长度
}
/*对i，j所在字符进行判断：
·如果相等，则i，j各进一步
·如果不相等，j进行回退，回退完之后再次比较
*/
if (s.charAt(i) == s.charAt(j)) {
j++;
}
//i标记的是当前所在的后缀字符，i在整轮循环中是不会变的，循环不变量
//j记录的是当前前后缀相等的字符串长度，因此把j的值记录进next数组中
next[i] = j;
}
}
}
459.重复的子字符串
题目描述：
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
解题方法：
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
if (len == 0) {
return false;
}
int[] next = new int[len];
getNext(next, s);
if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {
return true;
}
return false;
}
private void getNext(int[] next, String s) {
int j = 0;
next[0] = j;
//j初始化必须在0，i初始化必须在1
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i)) {
j = next[j - 1];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
next[i] = j;
}
}
}
/*
时间复杂度为O(n), n为字符串的长度；因为只匹配一遍
空间复杂度O(n)
*/
