Leetcode question brushing: String 07 (repeated substring)

459. Repeated substrings

Force button topic link

Given a non empty string , Determine whether it can be made up of a substring of it repeatedly . The given string contains only lowercase letters , And not longer than 10000.

Example 1:
Input : “abab”
Output : True
explain : By substring “ab” Repeat twice to form .

Example 2:
Input : “aba”
Output : False

Example 3:
Input : “abcabcabcabc”
Output : True
explain : By substring “abc” Repeat for four times . ( Or substrings “abcabc” Repeat twice to form .)

I didn't do it , See how complicated the problem is , Read the comment area and finally see one you can understand .
It's just violence , Before each interception i Characters , Copy len / i All over , Compare with the original string .

    public boolean repeatedSubstringPattern3(String s) {
    
        // String length 
        int len = s.length();
        // Substring , Does not contain itself 
        if (len < 2) {
    
            return false;
        }
        // List all possible 
        for (int i = 0; i <= len / 2; i++) {
    
            // If it's not divisible , It must not be composed of repeated strings 
            if (len % i != 0) {
    
                continue;
            }
            String temp = s.substring(0, i);
            String ans = "";
            for (int j = 0; j < len / i; j++) {
    
                // len/i  individual  temp  Strings are spliced together and compared with the original string 
                ans += temp;
            }
            if (s.equals(ans)) {
    
                return true;
            }
        }
        return false;
    }

There are also those big guys who submit in one line .

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

The hardest thing is this KMP How to write it

    public boolean repeatedSubstringPattern(String s) {
    
        if (s.equals("")) {
    
            return false;
        }
        int len = s.length();
        // Add a space to the original string （ sentry ）, Subscript from 1 Start , such j from 0 Start , You don't have to initialize 
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];
        // structure next Array ,j from 0 Start （ Space ）,i from 2 Start 
        for (int i = 2, j = 0; i <= len; i++) {
    
            // The match didn't work ,j  Back to the previous position ,next The value of the array 
            while (j > 0 && chars[i] != chars[j + 1]) {
    
                j=next[j];
            }
            if (chars[i] == chars[j + 1]) {
    
                j++;
            }
            // to update next The value of the array 
            next[i] = j;
        }

        if (next[len] > 0 && len % (len - next[len]) == 0) {
    
            return true;
        }
        return false;
    }