最长相等真前后缀最长相等前后缀也被称为 Border KMP算法就利用了其性质来进行匹配优化。前缀从字符串第一个字符开始的子串。后缀以字符串最后一个字符结束的子串。真长度严格小于原字符串长度。求法 (2)O(n2) def border(s): n len(s) L 0 for i in range(1, n): # 长度为 i 上限为 n-1 确保为真前后缀 if s[:i] s[n-i:n]: L i return L还有更加高效的算法可以优化到 ()O(n) 。正是这个优化产生了 KMP 算法。前缀函数在 KMP 中的前缀函数的到数组 π 其中 []π[i] 表示字符串的前缀 [0…]t[0…i] 中最长的相等真前后缀的长度。如果使用暴力枚举每个子串进行一次border函数的话时间复杂度是 (3)O(n3)b [] for i in range(len(s)): b.append(border(s[:i 1]))通过递推可以在 ()O(n) 时间内求出前缀数组 π假设我们正在计算 []π[i] 并且已知 [−1]π[i−1]j 。这意味着 [0…−1]t[0…j−1] 是 [0…−1]t[0…i−1] 的最长相等前后缀。情况A如果 [][]t[i]t[j] 那么 []1π[i]j1 。情况B如果 []≠[]t[i]t[j] 我们需要一个更短的相等前后缀。于是我们可以让 [−1]jπ[j−1] 然后重复 []t[i] 和 []t[j] 的比较过程直到匹配或 j 降为 00 。具体代码为def get_pi(s): n len(s) pi [0] * n for i in range(1, n): j pi[i - 1] # 取前一个的位置的pi while j 0 and s[i] ! s[j]: # 情况B j pi[j - 1] if s[i] s[j]: # 情况A j 1 pi[i] j return pi应用模式串匹配已知模式串 t 和匹配串 s 在预处理完模式串的 π 数组后可以通过双指针匹配。指针 i 始终在 s 上向右移动不回退。指针 j 在 t 上移动如果匹配j如果失配 j 根据 π 数组向左跳跳到一个可以让前面部分继续匹配的位置。这个根据 π 数组向左跳的过程可以理解成下面这句有名名的话一个人能走的多远不在于他在顺境时能走的多快而在于他在逆境时多久能找到曾经的自己。m, n len(t), len(s) pi get_pi(t) j 0 # 模式串指针 for i in range(n): # 文本串指针永不回退 while j 0 and s[i] ! t[j]: j pi[j - 1] if s[i] t[j]: j 1 if j m: # 匹配成功 # 位置为 i - j 1 0-based j pi[j - 1] # 继续匹配可能重叠的下一处求字符串周期先利用预处理的 π 数组求出所有的 Border 再根据这些 Border 就可以构造出所有的周期串了。求字符串所有周期由于 π 数组记录了最长 Border 而次长的 Border 可能通过 [[−1]−1]π[π[n−1]−1] 递归求得因此我们可以不断回跳求出所有的 Border 后周期就是 n - Border。n len(s) pi get_pi(s) b [] k pi[n - 1] while k: b.append(n - k) k pi[k - 1] b.append(n) print(*b)不要忘记了 s 自身也是周期然后每个周期串就是s[:b[i]]。完全循环在 [−1]0π[n−1]0 基础上当它的最小正周期−[−1]n−π[n−1] 可以被总长度 n 整除时存在完全循环。n len(s) pi get_pi(s) k n - pi[n - 1] print(YES if pi[n - 1] 0 and n % k 0 else NO)