459. Repeated Substring Pattern

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

如果input string可以從自身的substring重複組合成的話，string的第一個char就是重複substring的第一個char，string的最後一個char就是重複substring的最後一個char。把input string重複一次得到的新string去頭去尾後，如果能在其中找到input string的話，那麼這個input string就能被本身的substring重複組合成。

bool repeatedSubstringPattern(string s) { // time: O(n^2); space: O(n)
    if (s.empty()) return false;
    int n = s.size();
    string str = s.substr(1, n - 1) + s.substr(0, n - 1);
    return str.find(s) != string::npos;
}

bool repeatedSubstringPattern(string s) { // time: O(n^2); space: O(n)
    if (s.empty()) return false;
    int n = s.size();
    for (int len = 1; len <= n / 2; ++len) {
        if (n % len) continue;
        string pattern = s.substr(0, len);
        int i = len; // starting idx of 2nd pattern
        while (i + len <= n) {
            string substr = s.substr(i, len);
            if (substr != pattern) break;
            i += len;
        }
        if (i == n) return true;
    }
    return false;
}

bool repeatedSubstringPattern(string s) {
    if (s.empty()) return false;
    int n = s.size();
    for (int i = n / 2; i >= 1; --i) {
        if (n % i) continue;
        int c = n / i;
        string sub = s.substr(0, i), t;
        for (int j = 0; j < c; ++j) t += sub;
        if (t == s) return true;
    }
    return false;
}