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: TrueExplanation: It's the substring "ab" twice.

Example 2:

Input: "aba"Output: False

Example 3:

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

给定一个非空字符串，判断它是否可以通过自身的子串重复若干次构成。你可以假设字符串只包含小写英文字母，并且长度不会超过10000

解法1： 暴力法Brute Force

解法2：KMP，（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。

Java:  直接截取了重复验证

public class Solution {    public boolean repeatedSubstringPattern(String str) {        int n = str.length();        for(int i=n/2;i>=1;i--) {            if(n%i==0) {                int m = n/i;                String substring = str.substring(0,i);                StringBuilder sb = new StringBuilder();                for(int j=0;j

　　

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
     
       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] 686. Repeated String Match