题号459
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
暴力解法
class Solution {public boolean repeatedSubstringPattern(String s) {int size=s.length();int length=0;for(int i=1;i<=size/2;i++){if(size%i!=0)continue;String sub=s.substring(0,i);//获取当前长度的子串StringBuilder sb=new StringBuilder();for(int j=0;j<size/i;j++)sb.append(sub);//将获得的子串重复size/i次if(sb.toString().equals(s))//若得到和母串一样的结果return true;//则说明存在}return false;}
}两层for循环，先获取子串，再进行比对
移动匹配法
思路：
若字符串s为 abcabc
令s+s=ss为 abcabcabcabc
然后去掉首尾两个元素，即得到bcabcabcab
然后在该串中检索，是否存在s（abcabc)，若存在，则可以返回true
class Solution {public boolean repeatedSubstringPattern(String s) {int size=s.length();int length=0;StringBuilder sb=new StringBuilder();sb.append(s+s);sb.deleteCharAt(0);sb.deleteCharAt(size*2-2);String str=sb.toString();if(str.contains(s))return true;elsereturn false;}
}KMP法
思路：
若字符串s为 abcabcabc，则最长公共前后缀为abcabc
由推导可以得到，将整个串减去最长公共前后缀得到的就是最小重复单元
如果用整体长度除以该单元余数为0则返回true
class Solution {public boolean repeatedSubstringPattern(String s) {int size=s.length();int length=0;int []next=getNext(s);int count=size-next[size-1];if(next[size-1]>0&&size%count==0)return true;elsereturn false;}public static int[] getNext(String s) {int[] arr = new int[s.length()];arr[0] = 0;int j = 0;for (int i = 1; i < arr.length; i++) {//如果j和i对应字符不相等，那么将j移动到arr[j-1]的位置while (j > 0 && s.charAt(j) != s.charAt(i)) {j = arr[j - 1];}//如果相同，j先往前移动一格，再将arr[i]赋值if (s.charAt(j) == s.charAt(i)) {j++;arr[i] = j;}}return arr;}
})
