【LeetCode-简单题KMP】459. 重复的子字符串

题目

方法一：移动匹配

class Solution {//移动匹配public boolean repeatedSubstringPattern(String s) {StringBuffer str = new StringBuffer(s);//ababstr.append(s);//拼接一份自己  ababababstr.delete(0,1);// babababstr.delete(str.length()-1,str.length());//bababa//删除第一个字符和最后一个字符，不然在str里面匹配s时  直接就能从开头匹配就没有意义了//我们要的就是拼接起来的部分  也能匹配到原来的sif(str.toString().contains(s)) return true; // str: bababa   s: ababreturn false;}
}

方法二：KMP算法

关键代码
参考视频讲解字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串
参考题解：459.重复的子字符串—KMP解法

 // 最后判断是否是重复的子字符串，这里 next[len-1] 即代表next数组末尾的值if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {return true;}return false;

class Solution {//KMP算法public boolean repeatedSubstringPattern(String s) {if (s.length() == 0)   return false;int[] next = getNext(s);int len = s.length();// 最后判断是否是重复的子字符串，这里 next[len-1] 即代表next数组末尾的值if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {return true;}return false;}public int[] getNext(String s){int[] next = new int[s.length()];int j = 0;next[0]=j;for(int i = 1 ; i<next.length;i++){while(j> 0 && s.charAt(i) !=s.charAt(j)){j = next[j-1];}if(s.charAt(i) ==s.charAt(j)) j++;next[i] = j;}return next;}
}