459重复的子字符串

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

public repeatedSubstringPattern(String s){int n = s.length();for(int i = 1; i <= n / 2; i++){if(n % i != 0) continue;// substring获取子字符串是左闭右开的String ss = s.substring(0, i);boolean flag = true;for(int j = i; j < n; j += i){String sss = substring(j, j + i);if(!ss.equals(sss)) {flag = false;break;}}if(flag) return true;}return false;
}

复杂度：n*n

逆天方法，一行解决，还没看证明过程

public boolean repeatedSubstringPattern(String s){return (s + s).indexOf(s, 1) != s.length();
}

KMP待看