### 题目

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


### 思路

(1)常见的解决思路即尝试所有可能的子字符串。

(2)但还有一个rsrs3写的Easy python solution with explaination解法，一种递推的思路（感觉有点像线性代数里证明向量组的线性相关）。

Basic idea:

• First char of input string is first char of repeated substring
• Last char of input string is last char of repeated substring
• Let S1 = S + S (where S in input string)
• Remove 1 and last char of S1. Let this be S2
• If S exists in S2 then return true else false
• Let i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]

Let’s say T = S + S.

“S is Repeated => From T[1:-1] we can find S” is obvious.

• 如果在T[1:-1]中可以找到S，且index为p-1, 那么在T和S中的index为p

• s1 = S[:p], S可以被表示为s1X1, 因为S为重复字符串，所以S = X1s1 = s1X1 (A)

1. len(X1) < len(s1)
这种情况不存在，以为如果我们发现ST[1:-1]，则index应为len(X1)，而不是len(s1) = p

2. len(X1) == len(s1)
由A式可以推出X1 = s1，则S为重复的

3. len(X1) > len(s1)
因为A式，X1有前缀s1，可以表示为s1X2
X1 = s1X2，由A式得到s1s1X2 = s1X2s1, 即X2s1 = s1X2 (B)
这下就简洁明了了，依照前面的步骤递推，最终我们可以得到一个Xnlen(Xn) == len(s1) 并且 Xns1 = s1Xn => Xn = s1 => S = s1X1 = s1s1X2 = ... = s1s1...s1Xn-1 = s1s1...s1s1Xn => S is Repeated.

### Python代码

1、常见思路（尝试所有可能的子字符串）

2、非常精彩简洁