You need to enable JavaScript to run this app. Leetcode459题重复子串模式KMP前缀函数反向性质证明请求
优惠活动
大模型
产品
解决方案
定价
更多

Leetcode459题重复子串模式KMP前缀函数反向性质证明请求

前置定义对齐
  • 研究对象为LeetCode第459题涉及的字符串s,总长度为N,非空
  • KMP前缀函数值L:s中同时满足“是真前缀、是真后缀”的最长子串长度(真前缀/真后缀要求子串长度小于N,L=0代表不存在非空的公共真前后缀)
  • 待证反向命题:如果s确实可以由长度为K的最短重复单元拼接m次构成(即s=单元重复m次,m≥2,K是所有能构成s的重复单元中长度最小的值,满足K=N/m),那么s的前缀函数值L必然等于N-K
推导过程

第一步:确定L的下界

当s由长度为K的单元t重复m次构成时,s可以拆成连续m个完全相等的块:s = t_1 t_2 ... t_m,每个t_i都是长度为K、和t完全相同的子串。
此时很容易找到一个合法的公共前后缀:取长度为N-K的串——前缀部分是s去掉最后一个块t_m,内容为t_1 t_2 ... t_{m-1};后缀部分是s去掉第一个块t_1,内容为t_2 t_3 ... t_m。因为所有块完全相等,这两段逐位相同,因此N-K是一个合法的公共前后缀长度。
根据L的定义,L是所有合法公共前后缀中的最大值,因此必然满足:L ≥ N-K

第二步:确定L的上界

用反证法证明:不存在长度大于N-K的公共前后缀。
假设存在一个合法的公共前后缀长度L' > N-K。结合公共前后缀的基本属性:如果长度为L'的子串同时是s的真前缀和真后缀,那么s的前L'个字符和最后L'个字符逐位相等,对齐后就能推出,s中所有间隔p = N-L'位置的字符全部相等——也就是说整个s完全可以由长度为p的前缀重复拼接出来,p就是s的全局重复周期。
因为我们假设L' > N-K,代入可推出p = N-L' < K。这就意味着我们找到了一个比K更短的重复单元,能拼接得到完整的s,这和题设中“K是s的最短重复单元长度”的前提完全矛盾。
因此假设不成立,所有合法的公共前后缀长度都不会超过N-K,也就是L作为最长的公共前后缀,必然满足:L ≤ N-K

第三步:得出结论

结合上面两个方向的不等式:

  • L 不会小于 N-K
  • L 不会大于 N-K
    唯一可能的结果就是L = N-K
直观校验示例

取s = "abcabcabc",总长度N=9,最短重复单元K=3("abc")。按照结论L应该等于9-3=6。实际验证:

  • 长度为6的前缀是"abcabc",长度为6的后缀也是"abcabc",完全相等
  • 尝试找更长的公共前后缀(比如长度7):前缀是"abcabca",后缀是"bcabcab",逐位比对不相等
    因此实际的最长公共前后缀长度就是6,和推导结果完全一致。

内容的提问来源于stack exchange,提问作者llodds

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.11 17:24:03