> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/459.-repeated-substring-pattern.md).

# 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.)
```

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

```cpp
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;
}
```

```cpp
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;
}
```

```cpp
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;
}
```