String - 459. Repeated substrings

1 Title Description

Given a non empty string s , Check whether it can be formed by repeating one of its substrings multiple times .

2 Title Example

Example 1:
Input : s = “abab”
Output : true
explain : But by substring “ab” Repeat twice to form .

Example 2:
Input : s = “aba”
Output : false

Example 3:
Input : s = “abcabcabcabc”
Output : true
explain : But by substring “abc” Repeat for four times . ( Or substring “abcabc” Repeat twice to form .)

3 Topic tips

1 <= s.length <= 104
s It's made up of lowercase letters

4 Ideas

Method 1 ： string matching
We can put the string ss It's written in s’s’···s’s’ In the form of .

If we remove the string s Before n’ Characters （ That is, a complete s’), Then add these characters to the end of the remaining string in order , Then the resulting string is still s. because 1 ≤ n’≤ n, So if you put two s together , And remove the first and last characters , Then the obtained string — Must include s, namely s It's a substring of it .
So we can consider this method : We will have two s together , And remove the first and last characters . If s Is a substring of the string , that s Meet the requirements of the topic .
Proving requires some tricks of congruence operation , See after method 3 「 Proof of correctness 」 part . Let's assume that we have completed the proof , In this way, you can use very short code to complete this problem . In the following code , We can from the location 11 Start searching , And hope that the query result is not location nn, This is equivalent to removing the first and last characters of the string .

Complexity analysis

Because we use the string lookup function of the language , Therefore, there is no in-depth analysis of its space-time complexity .

Method 2 ：：KMP Algorithm
Because this question is to query whether another string appears in one string , You can apply it directly KMP Algorithm . So here's right KMP The algorithm itself will not be repeated . Readers can consult materials for learning .

5 My answer

class Solution {
    
    public boolean repeatedSubstringPattern(String s) {
    
        return (s + s).indexOf(s, 1) != s.length();
    }
}

class Solution {
    
    public boolean repeatedSubstringPattern(String s) {
    
        return kmp(s + s, s);
    }

    public boolean kmp(String query, String pattern) {
    
        int n = query.length();
        int m = pattern.length();
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
    
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
    
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
    
                fail[i] = j + 1;
            }
        }
        int match = -1;
        for (int i = 1; i < n - 1; ++i) {
    
            while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
    
                match = fail[match];
            }
            if (pattern.charAt(match + 1) == query.charAt(i)) {
    
                ++match;
                if (match == m - 1) {
    
                    return true;
                }
            }
        }
        return false;
    }
}