代码随想录第十一天（459）

459. 重复的子字符串

也不知道为啥这个提示简单题……

答案思路

暴力破解

例如：abcabc

移位一次：cabcab 移位两次：bcabca 移位三次：abcabc

现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串。

基于这个思想，可以每次移动k个字符，直到匹配移动 length - 1 次。但是这样对于重复字符串很长的字符串，效率会非常低。在 LeetCode 中执行时间超时了。

//暴力代码
public  boolean repeatedSubstringPattern(String s) {for(int i = 1; i < s.length(); i++) {String str = rotate(s.toCharArray(),i);if(s.equals(str)) return true;}return false;}public  String rotate(char[] nums, int k) {k = k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);return String.valueOf(nums);}public  void reverse(char[] nums, int begin, int end) {int i = begin, j = end;while(i < j) {char temp = nums[i];nums[i++] = nums[j];nums[j--] = temp;}}作者：Goodlucky
链接：https://leetcode.cn/problems/repeated-substring-pattern/solutions/114572/jian-dan-ming-liao-guan-yu-javaliang-xing-dai-ma-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

涉及到的知识点，equals和==之间的区别，String重写后的equals比较的是内容，而不重写equals时，两者是相同的，如果使用的是基本数据类型，比较的是值，如果是引用数据类型，比较的是地址。

移动匹配

当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：

也就是由前后相同的子串组成。

那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前后的子串做后串，就一定还能组成一个s，如图：

所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。

当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。

class Solution {public boolean repeatedSubstringPattern(String s) {String str = s + s;return str.substring(1, str.length() - 1).contains(s);
}
}作者：Goodlucky
链接：https://leetcode.cn/problems/repeated-substring-pattern/solutions/114572/jian-dan-ming-liao-guan-yu-javaliang-xing-dai-ma-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

substring(int beginIndex, int endIndex)方法截取字符串并返回其[beginIndex,endIndex-1]范围内的内容。
Java String contains（）方法用于检查字符串是否包含指定的字符序列。返回值为true或false。