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

今天第一题：力扣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; }}

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