重复的子字符串 | LeetCode-459 | 字符串匹配 | KMP | 双指针

🕹️KMP练习题

1.题目描述🍍

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• $1<=s.length<=10^4$
• s 由小写英文字母组成

2.题解🫐

2.1 暴力解法🍅

class Solution {public boolean repeatedSubstringPattern(String s) {int n = s.length();  // 获取字符串的长度// 枚举可能的子串长度，最大长度为字符串长度的一半for(int i = 1; i <= n / 2; i++) {// 如果字符串长度能被子串长度整除，说明可能由该长度的子串重复构成if(n % i == 0) {int j;// 检查从索引 i 开始的字符是否和子串的字符匹配for(j = i; j < n; j++) {// 如果当前字符与前面子串对应位置的字符不匹配，跳出循环if(s.charAt(j) != s.charAt(j - i)) break;}// 如果 j 遍历到了字符串的末尾，说明整个字符串可以由子串重复构成if(j == n) return true;}}// 如果没有找到满足条件的子串，返回 falsereturn false;}
}

2.2 KMP - 移动匹配🥭

2.2.1 内置函数🎃

class Solution {// 判断字符串 s 是否由一个子串重复组成public boolean repeatedSubstringPattern(String s) {// 将字符串 s 自身连接，并从索引 1 开始查找 s 的首次出现位置// 如果找到了且位置不等于 s 的长度，说明 s 是由一个子串重复组成return (s + s).indexOf(s, 1) != s.length();}
}

2.2.2 KMP实现🍇

class Solution {// 判断字符串 s 是否由一个子串重复组成public boolean repeatedSubstringPattern(String s) {int n = s.length(); // 获取字符串 s 的长度String goal = s; // 保存原始字符串s = s + s; // 将字符串 s 自身连接，形成新的字符串int[] next = getNext(goal); // 生成目标字符串的前缀函数数组int j = 0; // 初始化匹配指针，用于遍历目标字符串// 遍历新的字符串 s，直到 n*2-1 位置for (int i = 1; i < n * 2 - 1; i++) {// 当前字符不匹配时，根据前缀函数回退 jwhile (j > 0 && s.charAt(i) != goal.charAt(j)) j = next[j - 1];// 如果字符匹配，增加 jif (s.charAt(i) == goal.charAt(j)) j++;// 如果 j 达到目标字符串的长度，表示找到了重复子串if (j == n) return true;}return false; // 如果没有找到符合条件的重复子串，返回 false}// 生成前缀函数数组public int[] getNext(String s) {int n = s.length(); // 获取字符串 s 的长度int[] next = new int[n]; // 初始化前缀函数数组int j = 0; // 前缀指针next[0] = 0; // 第一个字符的前缀长度为 0// 遍历字符串，从第二个字符开始for (int i = 1; i < n; i++) {while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];// 当当前字符不匹配时，回退前缀指针 jif (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配，前缀长度增加next[i] = j;// 记录当前字符的前缀长度到 next 数组}return next; // 返回前缀函数数组}
}

2.3 KMP优化🍒

• 这个方法需要对种字符串的next数组的特征要了解，毛毛张在下面举几个例子
  • 正例： 字符串abababab的next数组：[0, 0, 1, 2, 3, 4, 5, 6]
  • 正例： 字符串ababcababcababc的next数组：[0, 0, 1, 2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  • 反例： 字符串abcabca的next数组：[0, 0, 0, 1, 2, 3, 4]

class Solution {public boolean repeatedSubstringPattern(String s) {int n = s.length(); // 获取字符串 s 的长度int[] next = getNext(s); // 生成字符串 s 的前缀函数数组int minLen = n - next[n - 1]; // 计算最小重复子串的长度//minLen < n 是为了防止这种情况:abcdef 此时minLen=0 // 如果最小长度小于字符串长度，并且字符串长度能够被最小长度整除，则存在重复子串if (minLen < n && n % minLen == 0) return true;return false; // 否则返回 false}// 生成前缀函数数组public int[] getNext(String s) {int n = s.length(); // 获取字符串 s 的长度int[] next = new int[n]; // 初始化前缀函数数组int j = 0; // 前缀指针next[0] = 0; // 第一个字符的前缀长度为 0// 遍历字符串，从第二个字符开始for (int i = 1; i < n; i++) {while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];// 当当前字符不匹配时，回退前缀指针 jif (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配，前缀长度增加next[i] = j;// 记录当前字符的前缀长度到 next 数组}return next; // 返回前缀函数数组}
}

3.相关练习🍑

• 找出字符串中第一个匹配项的下标 | LeetCode-28 | KMP算法 | next数组 | Java详细注释
• 旋转字符串 | LeetCode-796 | 模拟 | KMP | 字符串匹配

都看到这了，不妨一键三连再走吧！

🌈欢迎和毛毛张一起探讨和交流！
联系方式参见个人主页： 神马都会亿点点的毛毛张