题目描述
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
很明显这里所说的子串不包括自身
普通解法
以 s 表示给出的非空字符串，若 s 可由自身的子字符串重复构成，则子字符串长度最少为 1，最长为 len(s)//2
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
i,l=1,len(s)
while i<=l//2:
if l%i==0 and s[:i]*(l//i)==s:
return True
i+=1
return False
简洁解法
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return (s+s)[1:-1].find(s) != -1
初次看到这种写法，觉得真是太简洁以至于有点莫名其妙，想了一下才觉得提交人真的很聪明
以 s 表示给出的非空字符串，以 n 表示其子字符串，如果 n 存在，则 n 的长度最小为 1，重复次数最小为 2。
不妨以 len(n) 表示取字符串 n 长度，num(s,n) 表示 s 中 n 重复的次数。
证明若 n 存在，则 (s+s)[1:-1].find(s) != -1
取极限情况，即 len(n) 为 1，num(s,n) 为 2，则 num(s+s,n) 为 4，num(s+s[1:-1],n) 为 2，num(s+s[1:-1],s) 为 1，则有 (s+s)[1:-1].find(s) != -1 成立。
取一般情况，len(n)>1，num(s,n) 为 m(m>=2)，则 num(s+s,n) 为 2m，num(s+s[1:-1],n) 为 2m-2，num(s+s[1:-1],s) 为 2-(2/m)，因为 m>=2，则有 (s+s)[1:-1].find(s) != -1 成立。
证明若 (s+s)[1:-1].find(s) != -1，则 n 存在
反证法：假设 (s+s)[1:-1].find(s) != -1，且 n 不存在。
若 (s+s)[1:-1].find(s) != -1，以 x 表示 s 尾部匹配 s 头部的字符串长度。
若 len(s)%x==0，则有 s[-x:]==s[:x]==s[x:2*x]...==[-x:]，即 s 的重复子字符串为 n:s[:x]，即 n 存在；
若 len(s)%x!=0，则令 x=len(s)%x，若 len(s)%x==0，根据上一条推论，存在 n:s[:x]，若 len(s)%x!=0，则令 x=len(s)%x，递归执行，极限条件为 x 为 1，即 s 由同一个字符重复构成。因此若 (s+s)[1:-1].find(s) != -1，则 n 存在。
