给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例：

输入: "abab" 输出: True

解释: 它可以由子字符串 "ab" 重复两次构成。

二、方案一：暴力法

1、思路

• 检查从字符串长度的一半开始，依次递减的每个子字符串，看它是否可以重复多次构成原字符串。
• 如果找到这样的子字符串，则返回 True；否则，在检查完所有可能的子字符串后返回 False。

2、代码实现

func repeatedSubstringPattern(s string) bool {
    n := len(s)
    for i := n / 2; i > 0; i-- {
        if n % i == 0 {
            if strings.Repeat(s[:i], n/i) == s {
                return true
            }
        }
    }
    return false
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串的长度。最坏情况下，我们需要检查所有可能的子字符串。
• 空间复杂度：O(n)，用于存储重复的子字符串。

---

三、方案二：双指针法

1、思路

• 初始化两个指针，一个指向子字符串，一个遍历剩余节点
• 如果剩余节点均和相应的子字符相等，则返回 True

2、代码实现

func repeatedSubstringPattern(s string) bool {
	b := []byte(s)
	i, j := 0, 0
	// 子字符串最大长度：长度的1/2
	for i = 0; i < len(b)/2; i++ {
		// 遍历剩余节点
		for j = i + 1; j < len(b); j++ {
			if b[j] != b[j%(i+1)] {
				break
			}
		}
		// 遍历到字符串结尾并且长度是字符串的整数倍
		if j == len(b) && j%(i+1) == 0 {
			return true
		}
	}

	return false
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串的长度。
• 空间复杂度：O(1)

---

四、总结

方案	时间复杂度	空间复杂度	备注
暴力法	O(n^2)	O(n)	实现简单，但效率较低
双指针法	O(n^2)	O(1)	可读性高