重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode）

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

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

KMP

根据kmp算法中next数组的性质进行判断

如图所示，如果len % (len - (next[len - 1] )) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

特殊条件判断：next[len-1] = 0， 则len % (len - (next[len - 1] )) 恒等于0，故需要排除掉

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if(s.equals("")) return false;
        int[] next = getNext(s);
        int len = next.length;
        
        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;
        for(int i = 1; i < s.length(); i++){
            while(j > 0 && s.charAt(i) != s.charAt(j)){
                j = next[j-1]; //j回退到前一个字符串的next位置与i进行比较
            }
            if(s.charAt(i) == s.charAt(j)){
                j++; //最长相同前后缀+1
            }
            next[i] = j;
        }
        return next;
    }
}

位移方法

如果您的字符串 S 包含一个重复的子字符串，那么这意味着您可以多次 “移位和换行”`您的字符串，并使其与原始字符串匹配。

例如：abcabc

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

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

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

为了避免这种无用的环绕，可以创建一个新的字符串 str，它等于原来的字符串 S 再加上 S 自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么 str = S + S = acdacd

acd 移动的可能：dac、cda。其实都包含在了 str 中了。

一开始 acd (acd) ，移动一次 ac(dac)d，移动两次 a(cda)cd。循环结束

所以可以直接判断 str 中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String str = s + s;
        return str.substring(1, str.length()-1).contains(s);
    }
}