459

459. Repeated Substring Pattern (Easy)

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

 

Example 1:

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Example 2:

Input: s = "aba"
Output: false

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

Companies:
Google, Salesforce

Related Topics:
String, String Matching

Similar Questions:

• Implement strStr() (Easy)
• Repeated String Match (Medium)

Solution 1. Brute force

// OJ: https://leetcode.com/problems/repeated-substring-pattern/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int N = s.size();
        for (int len = 1; len <= N / 2; ++len) {
            if (N % len) continue;
            int i = len;
            for (; i < N; ++i) {
                if (s[i] != s[i % len]) break;
            }
            if (i == N) return true;
        }
        return false;
    }
};

Solution 2. Brute force with string_view

// OJ: https://leetcode.com/problems/repeated-substring-pattern/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string_view p = s, sv = s;
        for (int len = s.size() / 2; len >= 1; --len) {
            if (s.size() % len) continue;
            p = p.substr(0, len);
            int i = s.size() / len - 1;
            for (; i >= 0 && p == sv.substr(i * len, len); --i);
            if (i < 0) return true;
        }
        return false;
    }
};

Solution 3. KMP

// OJ: https://leetcode.com/problems/repeated-substring-pattern/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/repeated-substring-pattern/discuss/94397/C%2B%2B-O(n)-using-KMP-32ms-8-lines-of-code-with-brief-explanation.
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int N = s.size(), j = -1;
        vector<int> lps(N + 1, -1);
        for (int i = 1; i <= N; ++i) {
            while (j >= 0 && s[i - 1] != s[j]) j = lps[j];
            lps[i] = ++j;
        }
        return lps[N] && (lps[N] % (N - lps[N])) == 0;
    }
};