重复的子字符串（459）

题目

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

示例

输入: "abab" 输出: True

输入: "aba" 输出: False

输入: "abcabcabcabc" 输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

算法

枚举

如果字符串拥有子串，那么这个子串长度最大不超过字符串的一半，且字符串长度是子串长度的整数倍。

所以我们使用变量i表示子串长度，这个长度小于等于字符串长度一半且能被字符串长度整除

当i是个合理的值时，我们重复子串到字符串长度后比较是否和字符串相同，相同则返回true

export const repeatedSubstringPattern = (s) => {
	for (let i = 1; i <= s.length / 2; i++) {
		if (s.length % i !== 0) continue;
		const repeatedString = s.substring(0, i).repeat(s.length / i);
		if (repeatedString === s) return true;
	}
	return false;
};

双倍字符串

当一个字符串有子串时，那么将字符串旋转一定次数后，旋转后的字符串等于原字符串，比如对于字符串abcabcabc：abcabcabc -> bcabcabca -> cabcabcab -> abcabcabc

所以我们可以旋转这个字符串，判断和原字符串是否相同，但是这样时间复杂度比较高，我们可以通过构造双倍字符串来简化这个操作：

我们在原字符串基础上拼接一个原字符串，即s+s。然后我们维护一个大小为s.length的窗口，这个窗口不包括双倍字符串的第一项和最后一项，如果这个窗口内的字符串和原字符串相同，则说明存在子串返回true

export const repeatedSubstringPattern = (s) => {
	const doubleStr = s + s;
	for (let i = 1; i < s.length; i++) {
		const rotateStr = doubleStr.substring(i, s.length + i);
		if (rotateStr === s) return true;
	}
	return false;
};