力扣字符串专题：第六天，发现人真的有惰性呀，啥也不想干，躺平

力扣字符串专题：第六天，发现人真的有惰性呀，啥也不想干，躺平 今天第一题：力扣28题 解题思路：

摊牌了，不装了，这道题我选择不理解，就是背，哈哈哈！一些理解在代码注释中

代码如下：

class Solution {
    //获取next数组的方法
    public void getNext(int[] next, String s) {
        //第一步：初始化
        int j = -1;
        next[0] = j;
        //遍历模式串s
        for(int i = 1; i < s.length(); i++) {
            //第二步：处理前后缀不相同的情况
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)) {
                j = next[j];
            }
            //第三步：处理前后缀相同的情况
            if(s.charAt(i) == s.charAt(j+1)) {
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        //特判
        if(needle.length() == 0) {
            return 0;
        }
        //定义一个大小为needle字符串长的一个整数数组next
        int[] next = new int[needle.length()];
        //更新next数组
        getNext(next, needle);
        //定义模式串needle的起始位置，从-1开始，因为next数组就是从-1开始的
        int j = -1;
        //遍历文本串haystack，从0开始
        for(int i = 0; i < haystack.length(); i++) {
            //文本串和模式串不等时怎么处理？
            while(j >= 0 && haystack.charAt(i) != needle.charAt(j+1)) {
                j = next[j];
            }
            //文本串和模式串相等时怎么处理？
            if(haystack.charAt(i) == needle.charAt(j+1)) {
                j++;
            }
            //当j跑到了模式串的末尾，说明文本串里出现了模式串，因为题中要求返回出现的起始位置，所以返回i - needle.length() + 1
            if(j == needle.length() - 1) {
                return (i - needle.length() + 1);
            }
        }
        //如果跑完都没出现，说明就没有，返回-1
        return -1;
    }
}

同样遇到另一道题，思路大致相同，只是最后处理有一些不同，大同小异！

今天第二题：力扣459题

解题思路：感觉把KMP算法如何更新next数组的步骤记住就可以做题了，同28题，我这里写了两种方式
代码如下：

class Solution {
    //方法一，借鉴28题
    public void getNext(int[] next, String s) {
        //初始化
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.length(); i++) {
            //第二步：处理前后缀不相同的情况
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)) {
                j = next[j];
            }
            //第三步：处理前后缀相同的情况
            if(s.charAt(i) == s.charAt(j+1)) {
                j++;
            }
            next[i] = j;
        }
    }
    public boolean repeatedSubstringPattern(String s) {
        if(s.length() == 0) {
            return false;
        }
        int[] next = new int[s.length()];
        getNext(next, s);
        if(next[s.length()-1] != -1 && s.length() % (s.length() - (next[s.length()-1] + 1)) == 0) {
            return true;
        }
        return false;

        //方法二
        if(s.length() == 0) {
            return false;
        }
        int length = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
        s = " " + s;
        int[] next = new int[length + 1];
        // 构造 next 数组过程，j从0开始(空格)，i从2开始
        for(int i = 2, j = 0; i < length + 1; i++) {
            while(j > 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }
            if(s.charAt(i) == s.charAt(j+1)) {
                j++;
            }
            next[i] = j;
        }
        if(next[length] > 0 && length % (length - next[length]) == 0) {
            return true;
        }
        return false;
    }
}

不得不说，这题真不是给我这种凡夫俗子做的，哈哈哈，都是大佬！！！
到今天为止，字符串就先告一段落了，明天开始“双指针” 的学习，奥力给！！！