LeetCode459.重复的字符串

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

法一：KMP算法使用

class Solution {
   public boolean repeatedSubstringPattern(String s){
        int[] next = new int[s.length()];
        getNext(next,s);
        //最后一位最长相等前后缀为0，说明没有可重复的子串
        if(next[s.length() -1] == 0){
            return false;
        }else{
            //若最后一位最长相等前后缀不为0，s-最长相等前后缀的长度为可重复的子串，若可以被s整除则可一直循环此子串
            return s.length() % (s.length() - next[s.length() -1]) == 0;
        }
    }
    //next数组--求最长相等前后缀
    public void getNext(int[] next, String s){
        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;
        }
    }
}

法二：暴力枚举求解

双循环，i从1到n/2表示子串长度，j与j-i在i的循环内每次从i到n
如ababab，i=2时，令j=i，j与j-i同步向后遍历，若出现不同，则返回false。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {//双循环，i从1到n/2表示子串长度，j与j-i在i的循环内每次从i到n
        //如ababab，i=2时，令j=i，j与j-i同步向后遍历，若出现不同，则返回false。
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
}