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

``````class Solution {
public:
bool repeatedSubstringPattern(string str) {
int n = str.size();
for (int i = n / 2; i >= 1; --i) {
if (n % i == 0) {
int c = n / i;
string t = "";
for (int j = 0; j < c; ++j) {
t += str.substr(0, i);
}
if (t == str) return true;
}
}
return false;
}
};
``````

``````class Solution {
public:
bool repeatedSubstringPattern(string str) {
int i = 1, j = 0, n = str.size();
vector<int> dp(n + 1, 0);
while (i < n) {
if (str[i] == str[j]) dp[++i] = ++j;
else if (j == 0) ++i;
else j = dp[j];
}
return dp[n] && (dp[n] % (n - dp[n]) == 0);
}
};
``````

Implement strStr()

Repeated String Match

https://discuss.leetcode.com/topic/68498/one-line-with-regex/2

https://discuss.leetcode.com/topic/67992/java-simple-solution-with-explanation

https://discuss.leetcode.com/topic/67652/c-o-n-using-kmp-32ms-8-lines-of-code-with-brief-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation