題目描述
給定一個非空的字符串漠嵌，判斷它是否可以由它的一個子串重復(fù)多次構(gòu)成咐汞。給定的字符串只含有小寫英文字母，并且長度不超過10000儒鹿。
示例 1:
輸入: "abab"
輸出: True
解釋: 可由子字符串 "ab" 重復(fù)兩次構(gòu)成化撕。
示例 2:
輸入: "aba"
輸出: False
示例 3:
輸入: "abcabcabcabc"
輸出: True
解釋: 可由子字符串 "abc" 重復(fù)四次構(gòu)成。 (或者子字符串 "abcabc" 重復(fù)兩次構(gòu)成约炎。)
很明顯這里所說的子串不包括自身
普通解法
以 s 表示給出的非空字符串植阴，若 s 可由自身的子字符串重復(fù)構(gòu)成蟹瘾，則子字符串長度最少為 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，重復(fù)次數(shù)最小為 2做祝。
不妨以 len(n) 表示取字符串 n 長度砾省，num(s,n) 表示 s 中 n 重復(fù)的次數(shù)。
證明若 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 存在
反證法：假設(shè) (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 的重復(fù)子字符串為 n:s[:x]，即 n 存在锉屈；
若 len(s)%x!=0荤傲，則令 x=len(s)%x，若 len(s)%x==0颈渊，根據(jù)上一條推論遂黍，存在 n:s[:x]终佛，若 len(s)%x!=0，則令 x=len(s)%x雾家，遞歸執(zhí)行铃彰，極限條件為 x 為 1，即 s 由同一個字符重復(fù)構(gòu)成芯咧。因此若 (s+s)[1:-1].find(s) != -1牙捉，則 n 存在。
