459. 重复的子字符串
459. 重复的子字符串
459. 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
- 1 < = s . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
- s 由小写英文字母组成 s 由小写英文字母组成 s由小写英文字母组成
思路：
如果一个长度为 n n n 的字符串 s s s 可以由它的一个长度为 n ′ n′ n′的子串 s ′ s′ s′重复多次构成，那么：
- n 一定是 n ′的倍数 n 一定是 n′的倍数 n一定是n′的倍数；
- s ′一定是 s 的前缀 s′一定是 s 的前缀 s′一定是s的前缀；
- 对于任意的 i ∈ [ n ′ , n ) ，有 s [ i ] = s [ i − n ′ ] 对于任意的 i∈[n′,n)，有 s[i]=s[i−n′] 对于任意的i∈[n′,n)，有s[i]=s[i−n′]。
也就是说， s s s 中长度为 n ′ n′ n′ 的前缀就是 s ′ s′ s′，并且在这之后的每一个位置上的字符 s [ i ] s[i] s[i]，都需要与它之前的第 n ′ n′ n′个字符 s [ i − n ′ ] s[i−n′] s[i−n′] 相同。
因此，我们可以从小到大枚举 n ′ n′ n′，并对字符串 s s s 进行遍历，进行上述的判断。注意到一个小优化是，因为子串至少需要重复一次，所以 n ′ n′ n′不会大于 n n n 的一半，我们只需要在 [ 1 , n / 2 ] [1, n/2] [1,n/2]的范围内枚举 n ′ n′ n′即可。
Go代码
func repeatedSubstringPattern(s string) bool {n := len(s)for i := 1; i * 2 <= n; i++ {if n % i == 0 {match := truefor j := i; j < n; j++ {if s[j] != s[j - i] {match = falsebreak}}if match {return true}}}return false
}
