Loading... 这个题目就是需要判断给定字符串能否由多个相同子串构成，如果可以就返回true。 # 构造 一种比较巧妙的方法是将s拼接两次，变成2s，然后掐头去尾，剩下的部分如果包含原本的s，说明是可以由子串构成，因为一旦字符串存在重复的构成，就一定在对应的偏移存在构成，例如 abcabc->abcabcabcabc->bcabcabcab，这里面是会有abcabc的。 ```go func repeatedSubstringPattern(s string) bool { ss := s+s ss = ss[1:len(ss)-1] return strings.Contains(ss, s) } ``` # KMP 另一种方法则是通过KMP的next数组。 > 对字符串 s[0:i]，我们定义 next[i] 表示该子串的 最长的 proper prefix（真前缀）和 proper suffix（真后缀） 的长度。 这里的前后缀长度实际上在 next[n-1] 就会等于对应的最长前后缀长度，比如 abcabc，就会是 abc 的长度，所以 n - next[n-1] 就是对应的最小重复子串长度，如果这部分长度能被字符串长度整除，说明这个字符串可以由重复子串构造。 ```go func repeatedSubstringPattern(s string) bool { n := len(s) next := make([]int, n) j := 0 for i := 1; i < n; i++ { for j > 0 && s[j] != s[i] { j = next[j-1] } if s[j] == s[i] { j++ } next[i] = j } lps := next[n-1] return lps > 0 && n % (n-lps) == 0 } ``` Last modification：July 21, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
