https://leetcode.cn/problems/repeated-substring-pattern/description/

<aside> 💡

KMP思路： 如果主串能够由重复子字符串组成，那么最长相等前后缀中不包含的那部分就是最小重复单元（需要一定数学推理）

• 推理过程见：https://programmercarl.com/0459.重复的子字符串.html#思路

实现：求主串长度与最长相等前后缀长度的差值，如果该差值能被主串长度整除则说明成立

</aside>

bool repeatedSubstringPattern(string s) {
	int n = s.size();
	vector<int> next(n, 0);
	int j = 0;

	// 求next数组，最后一个元素的next值就是最长相等前后缀长度
	for (int i = 1; i < n; ++i) {
		while (j > 0 && s[i] != s[j])
			j = next[j - 1];
		if (s[i] == s[j])
			next[i] = ++j;
	}
	int ans = n - next[n - 1];

	// 两个条件
	return ans < n && n % ans == 0;
}