[代码随想录] 第八天

28. 找出字符串中第一个匹配项的下标[https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/]
思路:KMP算法，重点在于求NEXT数组。还不能理解..暂时先背下来了。

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()>haystack.length()){
            return -1;
        }
        int[] next = getNext(needle);
        for (int i = 0, j = 0; i < haystack.length();) {
            while (j < needle.length()&& i < haystack.length() && needle.charAt(j) == haystack.charAt(i)) {
                i++;
                j++;
            }

            if (j == needle.length()) {
                return i - needle.length();
            } else if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
        return -1;
    }

    public int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

个人的代码比较啰嗦，但更符合自己的思路。。
**-----------------------分割线-------------------------**

459.重复的子字符串[https://leetcode.cn/problems/repeated-substring-pattern/description/]
思路：KMP思路看不懂，我选择穷举。