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.)
给定一个非空字符串，判断它是否可以通过自身的子串重复若干次构成。你可以假设字符串只包含小写英文字母，并且长度不会超过10000
解法1： 暴力法Brute Force
解法2：KMP，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。
Python:
class Solution(object):
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
size = len(str)
for x in range(1, size / 2 + 1):
if size % x:
continue
if str[:x] * (size / x) == str:
return True
return False
Python: KMP
class Solution(object):
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
size = len(str)
next = [0] * size
for i in range(1, size):
k = next[i - 1]
while str[i] != str[k] and k:
k = next[k - 1]
if str[i] == str[k]:
next[i] = k + 1
p = next[-1]
return p > 0 and size % (size - p) == 0
C++:
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;
}
};
C++:
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);
}
};
类似题目：
[LeetCode] 28. Implement strStr() 实现strStr()函数
[LeetCode] 686. Repeated String Match