459. 重复的子字符串 （精选）

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 暴力法：找出第一个与第一个字符相等的  -》判断此字符后面一直到结尾 是否满足  [j]==[j/找出的字符到开头的长度]
        //   改进：不用找第一个字符相等的，直接从1开始枚举i，直到 s.length/2
 
        //发现偶数的情况好搞，将字符串*2   转为偶数个 组成串
        //  调用indexof函数         去掉头和尾的一个字符  如果还能找到s，说明满足条件  -》需要数学证明的
        //可以设s的发现位置为i  数学证明是可行的
        //return (s + s).indexOf(s, 1) != s.length();
 
        //kmp算法  利用的是kmp自己实现indexof函数   但是奇数还是不好处理  还是将其*2 
        
 
        //暴力法
        int n=s.length();
        for(int i=1;i<n;i++){
            if(n%i==0){
                boolean f=true;
                for(int j=i;j<n;j++){
                    if(s.charAt(j)!=s.charAt(j-i)){
                        f=false;
                    }
                }
 
                if(f){
                    return true;
                }
            }
        }
 
 
        return false;
 
        
    }
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 暴力法：找出第一个与第一个字符相等的  -》判断此字符后面一直到结尾 是否满足  [j]==[j/找出的字符到开头的长度]
        //   改进：不用找第一个字符相等的，直接从1开始枚举i，直到 s.length/2
 
        //发现偶数的情况好搞，将字符串*2   转为偶数个 组成串
        //  调用indexof函数         去掉头和尾的一个字符  如果还能找到s，说明满足条件  -》需要数学证明的
        //可以设s的发现位置为i  数学证明是可行的
        //return (s + s).indexOf(s, 1) != s.length();
 
        //kmp算法  利用的是kmp自己实现indexof函数   但是奇数还是不好处理  还是将其*2 
        
 
        return (s + s).indexOf(s, 1) != s.length();
       
 
        
    }
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 暴力法：找出第一个与第一个字符相等的  -》判断此字符后面一直到结尾 是否满足  [j]==[j/找出的字符到开头的长度]
        //   改进：不用找第一个字符相等的，直接从1开始枚举i，直到 s.length/2
 
        //发现偶数的情况好搞，将字符串*2   转为偶数个 组成串
        //  调用indexof函数         去掉头和尾的一个字符  如果还能找到s，说明满足条件  -》需要数学证明的
        //可以设s的发现位置为i  数学证明是可行的
        //return (s + s).indexOf(s, 1) != s.length();
 
        //kmp算法  利用的是kmp自己实现indexof函数   但是奇数还是不好处理  还是将其*2 
        
 
        //kmp
        if(s.length()==1){
            return false;
        }
 
        String t=s+s;
        t=t.substring(1,2*s.length()-1);
       
       //求t的next数组               求的是s的，不是t的
        int[] next=new int[t.length()];
        next[0]=0;
        int val=0;
       for(int i=1;i<s.length();i++){
           while(val>0 && s.charAt(val)!=s.charAt(i)){
               val=next[val-1];
           }
            
           if(s.charAt(i)==s.charAt(val)){
               val++;
           }
            next[i]=val;
       }
 
 
        int j=0;
        for(int i=0;i<t.length();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;
 
 
 
        
    }
}