字符串 下【KMP再续】

⚡刷题计划day9继续，可以点个免费的赞哦~

往期可看专栏，关注不迷路，

您的支持是我的最大动力🌹~

今天的重头戏是KMP算法的理解，如果是第一次接触可能会有难度，可以结合以下链接的讲解及对应视频，没有明白可以多看多听几遍，加油！然后下一期就是双指针专题了，欢迎点赞收藏关注！

(programmercarl.com)

题目一：28. 找出字符串中第一个匹配项的下标

leetcode：28. 找出字符串中第一个匹配项的下标

(https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/)

法一：一般思路

法一就是暴力解，直接遍历两个串，比较是否匹配。

详见注释

class Solution {public int strStr(String haystack, String needle) {// 获取haystack和needle的长度int n1 = haystack.length();int n2 = needle.length();
​// 如果haystack的长度小于needle的长度，直接返回-1，表示找不到if(n1 < n2){return -1;}
​// 将haystack和needle转换为字符数组char[] c1 = haystack.toCharArray();char[] c2 = needle.toCharArray();
​// 遍历haystackfor(int i = 0; i < n1; i++){// 初始化搜索的起始和结束索引int start = i;int end = i + n2 - 1;// 如果结束索引超出haystack的范围，跳出循环if(end >= n1){break;}
​// 初始化一个标志位，用于判断是否找到匹配的子串boolean flag = true;int k = 0;// 内层循环，用于比较字符while(start <= end){// 如果当前字符不匹配，设置标志位为false并跳出循环if(c1[start++] != c2[k++]){flag = false;break;}}// 如果标志位为true，表示找到了匹配的子串，返回当前索引iif(flag){return i;}}
​// 如果遍历完haystack都没有找到needle，返回-1return -1;}
}

法二：KMP算法

详见注释

class Solution {// getNext 方法用于构建 next 数组，该数组用于存储模式字符串的最长前后缀匹配的长度public void getNext(int[] next, String s) {int j = -1; // j 用于记录当前比较的子字符串的最后一个匹配位置next[0] = j; // 模式字符串的第一个字符没有前缀，所以它的 next 值是 -1for (int i = 1; i < s.length(); i++) { // 从模式字符串的第二个字符开始遍历while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { // 当前字符不匹配时，尝试回溯j = next[j]; // 根据 next 数组回溯到上一个匹配的位置}if (s.charAt(i) == s.charAt(j + 1)) { // 如果当前字符匹配，更新 jj++;}next[i] = j; // 更新 next 数组，存储当前位置的最长前后缀匹配的长度}}
​// strStr 方法用于在 haystack 字符串中查找 needle 字符串出现的位置public int strStr(String haystack, String needle) {if (haystack.length() < needle.length()) { // 如果文本字符串比模式字符串短，直接返回 -1return -1;}
​int[] next = new int[needle.length()]; // 创建 next 数组getNext(next, needle); // 构建 next 数组
​int j = -1; // 初始化 j 为 -1，表示在模式字符串中的位置for (int i = 0; i < haystack.length(); i++) { // 遍历文本字符串while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) { // 如果当前字符不匹配，根据 next 数组回溯j = next[j]; // 回溯到上一个匹配的位置}if (haystack.charAt(i) == needle.charAt(j + 1)) { // 如果当前字符匹配，更新 jj++;}if (j == needle.length() - 1) { // 如果 j 到达模式字符串的末尾，表示找到了匹配return (i - needle.length() + 1); // 返回模式字符串在文本字符串中的起始位置}}
​return -1; // 如果遍历完文本字符串都没有找到匹配，返回 -1}
}

题目二：459.重复的子字符串

459.重复的子字符串

(https://leetcode.cn/problems/repeated-substring-pattern/description/)

法一：暴力解法

解题思路：

如果字符串 S 包含一个重复的子字符串，则可以通过多次移位原字符串，最终能得到一新相同字符串与原字符串匹配。

例：abcabc

移位一次：cabcab 移位两次：bcabca 移位三次：abcabc

现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串。

但是对于重复字符串比较长的情况，效率就会很低，并且超时。

基于此思想，可以新建一个字符串str = s + s，等于原字符串s再加上自身，这样新的字符串str就包含了所有移动的情况。

比如字符串：s = acd，那么 str = s + s = acdacd

acd 移动的可能：dac、cda。其实都包含在了 str 中了。就像一个滑动窗口

一开始 acd (acd) ，移动一次 ac(dac)d，移动两次 a(cda)cd。循环结束.

注意需要去除 str 中首尾元素

 所以可以直接判断之后，是否包含自身元素。如果包含。则表明存在重复子串。

附一网友理解：如果S不包含重复的子字符串，则S本身就是所谓的“重复子字符串”（这里方便自己理解，视为重复一次，不深究= =），str = S+S,说明S是str的重复子字符串，刨去str首尾两个字符之后（相当于分别破坏前一个S头部和后一个S尾部），不能满足str包含S。

AC代码

class Solution {public boolean repeatedSubstringPattern(String s) {String t = s + s;t = t.substring(1, t.length() - 1); 	// 掐头去尾if (t.contains(s)) {return true;}return false;}
}

法二：KMP

关于kmp还不是很理解的可以再康康上期附送的链接，这里不再多叙述

然后此题需要证明，有兴趣的小伙伴也可以康康这个链接：

(https://programmercarl.com/0459.重复的子字符串.html#思路)

我们这里直接给出判断的结论：

如果len % (len - (next[len - 1] + 1)) == 0 ，即数组的长度正好可以被 最长相等前后缀不包含的子串的长度 整除 ，说明该字符串有重复的子字符串。

class Solution {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.equals("")) return false;int len = s.length();int j=-1;int[] next = new int[len];getNext(next,s);////1.如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀//2.最长相等前后缀的长度为：next[len - 1] + 1。(这里的next数组是以统一减一的方式计算的，因此需要+1//3.len - (next[len - 1] + 1) 是最长相等前后缀不包含的子串的长度。if(next[len-1] != -1 && len % (len-(next[len-1]+1))==0){return true;}return false;}
}

下期开启新专题，感谢点赞收藏关注哦🌹