字符串系列最后两题，地狱 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)

*/