在一个串中查找是否出现过另一个串， 这是KMP的看家本领。那么寻找重复子串怎么也涉及到KMP算法了呢？ **KMP算法中next数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。** 前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。 那么 最长相同前后缀和重复子串的关系又有什么关系呢？ - 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串； - 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。 ``` 定理陈述 ═══════ 给定字符串 s，长度为 n。s 可以由某个子串重复构成，当且仅当： next[n-1] != 0 且 n % (n - next[n-1]) == 0 其中 next[n-1] 是 KMP 算法中字符串 s 的最长相等前后缀的长度。 符号定义 ═══════ 设： p = next[n-1] — 最长相等前后缀的长度 q = n - p — 去掉最长相等前后缀后剩余部分的长度 根据 next 数组的定义，p 满足： s[0:p] == s[n-p:n] （前缀与后缀相等） 且不存在比 p 更大的值也满足此条件。 字符串示意图： 位置: 0 ... p-1 | p ... n-p-1 | n-p ... n-1 内容: [ 前缀(p个) ] [ 中间部分 ] [ 后缀(p个) ] |←— q = n-p —→| 充分性证明（p != 0 且 n % q == 0 ⇒ s 可由重复子串构成） ════════════════════════════════════════════════════ 已知：p != 0 且 n % q == 0 要证：s 可由长度为 q 的子串 t 重复 n/q 次构成 证： 1. 由 p = n - q 和 next 数组定义知： s[0:n-q] == s[q:n] 即 s[i] = s[i+q]，对所有 0 ≤ i < n-q 成立。 这意味着相隔 q 个位置的字符都相等。 2. 由 n % q == 0，设 n = k·q（k 为整数）。 对任意位置 i，利用周期性： s[i] = s[i+q] = s[i+2q] = ... = s[i+(k-1)q] 因此整个字符串以 q 为周期。 3. 设 t = s[0:q]，则： s = s[0:q] + s[q:2q] + ... + s[(k-1)q:kq] = t + t + ... + t （共 k 次） ✅ 充分性得证。 必要性证明（s 可由重复子串构成 ⇒ p != 0 且 n % q == 0） ════════════════════════════════════════════════════ 已知：s 由长度为 m 的子串 u 重复 k 次构成（k ≥ 2），即 n = k·m 要证：p != 0 且 n % (n-p) == 0 证： 1. 证明 p ≥ n-m > 0： 考虑长度为 n-m 的前缀和后缀： 前缀：s[0 : n-m] = u 重复 k-1 次 后缀：s[m : n] = u 重复 k-1 次 两者相等，故 s 至少有一个长度为 n-m 的相等前后缀。 所以最长相等前后缀长度 p ≥ n-m > 0。 2. 证明 n % (n-p) == 0： 设 q = n-p，由 p ≥ n-m 知 q ≤ m。 反证法：假设 n % q ≠ 0，设 r = n % q（0 < r < q）。 由 p 的定义，s[0:p] == s[q:n]，即 s[i] = s[i+q]（0 ≤ i < n-q）。 这说明 q 是 s 的一个周期。 s 同时有两个周期：q 和 m（因 s 由 u 重复构成，m 自然是周期）。 由周期引理（Periodicity Lemma / Fine-Wilf 定理）： "若字符串同时具有周期 q 和周期 m，且 q + m ≤ n + gcd(q,m)，则该字符串以 gcd(q,m) 为周期" 这里 gcd(q,m) ≤ q 且 gcd(q,m) ≤ m。 可以构造出比 p 更长的相等前后缀（长度为 n - gcd(q,m)）， 这与 p 是"最长"相等前后缀矛盾。 因此假设不成立，必有 n % q == 0。 ✅ 必要性得证。 结论 ════ 综合充分性和必要性，严格证明了： 字符串 s 可由某个子串重复构成 ⇔ next[n-1] != 0 且 n % (n - next[n-1]) == 0 对应到代码： p = nextval[-1] — 最长相等前后缀长度 q = n - p — 最小重复单位的候选长度 return p != 0 and n % q == 0 — 判断是否满足定理条件 时间复杂度：O(n)，空间复杂度：O(n) ``` ```python class Solution: def repeatedSubstringPattern(self, s: str) -> bool: n = len( s ) # 1 <= s.length <= 10e4 nextval = [ 0 for _ in range( n ) ] def init_nextval(): j = 0 for i in range( 1, n ): while j > 0 and s[ i ] != s[ j ]: j = nextval[ j - 1 ] if s[ i ] == s[ j ]: j += 1 nextval[ i ] = j init_nextval() max_equal_fix_size = nextval[ -1 ] # 最大相同前后缀长度 exclude_fix_size = n - max_equal_fix_size # 不包含子串的长度 return max_equal_fix_size != 0 and n % exclude_fix_size == 0 ```