代码随想录算法训练营第八天 | LeetCode 28(实现strStr()) LeetCode 459(重复的子字符串)
28:实现strStr()
class Solution {
public int strStr(String haystack, String needle) {
//构造next数组
int[] next = new int[needle.length()];
getNext(next, needle);
int j = -1;
for(int i = 0; i < haystack.length(); i++){
//将haystack[i]与needle[j + 1]进行匹配
//若冲突 则 j 指针回退
//重复该方法至不发生冲突
while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
j = next[j];
}
//不冲突 继续匹配
if(haystack.charAt(i) == needle.charAt(j+1)){
j++;
}
//匹配完成
if(j == needle.length()-1){
//返回当前 i - needle长度 + 1 即为匹配子串的索引起点
return (i-needle.length()+1);
}
}
return -1;
}
//构造next数组 统一减一
public void getNext(int[] next, String s){
// j 代表着前缀末尾-1 且 是 最长相等前后缀的长度 - 1
int j = -1;
//第一位为 -1 第一位元素不存在 最长相等前后缀
next[0] = j;
//从数组索引1开始 i 为 后缀末尾
for (int i = 1; i < s.length(); i++){
//发生冲突 且 索引 j 未回退到起点 即 -1
//重复该操作 直到不冲突或 j回到起点
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;
}
}
}
459:重复的子字符串
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
int[] next = new int[len];
getNext(next, s);
/**
* 假设字符串s使用多个重复子串构成（这个子串是最小重复单位），
* 重复出现的子字符串长度是x，所以s是由n * x组成。
* 因为字符串s的最长相同前后缀的长度一定是不包含s本身，
* 所以 最长相同前后缀长度必然是m * x，而且 n - m = 1，
* 所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。
*
* 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，
* 如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
*/
// next[len - 1] 为 0，则代表整个串的最长相同前后缀长度为0
// 也就是代表着它一定不是重复子串构成的
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
return true;
}
return false;
}
//构造next数组 不减一
public void getNext(int[] next, String s){
// j 代表着前缀末尾 且 是 最长相等前后缀的长度
int j = 0;
//第一位为0 第一位元素不存在 最长相等前后缀
next[0] = j;
//从数组索引1开始 i 为 后缀末尾
for (int i = 1; i < s.length(); i++){
//发生冲突 且 索引 j 未回退到起点 即 -1
//重复该操作 直到不冲突或 j回到起点
while(j > 0 && s.charAt(i) != s.charAt(j)){
j=next[j - 1];
}
//前后缀相同
if(s.charAt(i) == s.charAt(j)){
j++;
}
//赋值
next[i] = j;
}
}
}
总结
今天两题都是基于KMP算法解题
我认为KMP算法其实挺容易理解但是它会比较难于代码实现，特别是构造前缀表
那么如何构造前缀表呢？
- 初始化 这里选择前缀表统一减一
int j = -1;
next[0] = j;
- 处理前后缀不同的情况
// 前后缀不相同了
while (j >= 0 && s[i] != s[j + 1]) {
// 向前回退
j = next[j];
}
- 处理前后缀相同情况
// 找到相同的前后缀
if (s[i] == s[j + 1]) {
j++;
}
next[i] = j;
- 完整的代码
//构造next数组 统一减一
public void getNext(int[] next, String s){
// j 代表着前缀末尾-1 且 是 最长相等前后缀的长度 - 1
int j = -1;
//第一位为 -1 第一位元素不存在 最长相等前后缀
next[0] = j;
//从数组索引1开始 i 为 后缀末尾
for (int i = 1; i < s.length(); i++){
//发生冲突 且 索引 j 未回退到起点 即 -1
//重复该操作 直到不冲突或 j回到起点
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;
}
}