给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
解题思路：
1.如果s存在重复字串，则将t掐头去尾以后，一定还存在一个s；
2.先去掉t的首尾字符(下标从1开始，到length-2结束)；
3.找t中是否存在一个s。
public class title459 {
public static void main(String[] args) {
String s="ababab";
boolean result = repeatedSubstringPattern(s);
System.out.println(result);
}
public static boolean repeatedSubstringPattern(String s) {
String t=s+s;
int j=0;
int[] next=getNext(s);
for(int i=1;i<t.length()-1;i++) {
while(j>0&& t.charAt(i)!=s.charAt(j)) {
j=next[j-1];
}
if(t.charAt(i)==s.charAt(j)) {
j++;
}
if(j==s.length()){
return true;
}
}
return false;
}
//求next数组
public static int[] getNext(String s) {
int[] next = new int[s.length()];
int j=0;
next[0]=0;
for(int i=1;i<s.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;
}
}
