刷 LeetCode 刷到 1392 这道 Hard 题的时候我第一反应是最长快乐前缀这名字起得有点唬人仔细读了一遍题目才发现它问的就一件事给定一个字符串找出一个最长的子串它既是整个字符串的前缀又是整个字符串的后缀而且不能是字符串本身。就这么一个概念官方给的标签是 Hard实际上核心考点就一个——KMP 算法里的前缀函数也就是 next 数组。字符串类题目里这道题非常适合用来检验你到底是背过 KMP 模板还是真懂 KMP 原理所以我把我的完整思考过程、三种解法、以及踩过的坑都整理出来给准备刷字符串专题的同学一个参考。1. 快乐前缀的定义到底在求什么1.1 一个名词拆开看先说清楚快乐前缀的名词来源。这个概念最早出现在 Codeforces 的一道题里LeetCode 1392 借用了这个名称。定义拆开就两条它是一个前缀也就是从字符串开头开始的一段连续子串它同时是一个后缀也就是从字符串末尾往前的一段连续子串题目特意强调非本身也就是这个子串的长度必须小于整个字符串的长度在字符串算法里同时是前缀和后缀的子串有一个更通用的名字叫border中文论坛里有人翻译成边缘子串或者边界前缀后缀。所以 1392 这道题翻译成人话就是求字符串最长公共真前后缀返回这个子串本身返回空串如果不存在。这里最容易忽略的一个细节是真字。前缀必须是真前缀后缀必须是真后缀也就是说你至少得空出一个字符来。比如 s a 的时候唯一的非空前缀是 a唯一的非空后缀也是 a但它俩就是字符串本身所以答案不是 a而是空串。这个边界条件我在第一次提交时踩过后面第 5 节会展开讲。1.2 拿题目示例走一遍用题目自带的例子 s level 来验证一下理解前缀集合、l、le、lev、leve后缀集合、l、el、vel、evel交集排除空串和自身l所以答案就是 l长度 1。再试一个我习惯手算的用例 s ababab前缀a、ab、aba、abab、ababa后缀b、ab、bab、abab、babab公共项ab、abab最长的是 abab长度 4这题如果用手工枚举确实不难但 LeetCode 的数据范围是字符串长度最长 10 的 5 次方手工枚举的思路翻译成暴力代码就完全不够用了。1.3 为什么这道题被标成 Hard我说句实在话这道题在 Hard 里属于纸老虎类型。它不涉及复杂的贪心策略、没有困难的推导过程、也用不到线段树这种高级数据结构它难就难在如果你不知道 KMP 的前缀函数你会陷入 O(n²) 的暴力思路里出不来如果你知道前缀函数这题就是一道模板题10 分钟之内能写完提交。我觉得 LeetCode 把这类题标成 Hard本质上是在测试你知识迁移的能力。你要能在一个看起来花里胡哨的概念快乐前缀背后识别出它本质上是最长相等前后缀然后想到前缀函数正好就是干这事的。这个识别过程才是 Hard 的真正难点。很多人在面试里被这题卡住不是不会写 KMP而是压根没想到要往 KMP 上想。2. 暴力写法为什么必挂复杂度分析2.1 最简单粗暴的写法刚看到这题正常人第一反应都是从大到小尝试。既然要找最长的那就先试长度为 n-1 的子串能不能作为快乐前缀不行再试 n-2依此类推找到第一个就直接返回。def longestPrefix(self, s: str) - str: n len(s) for k in range(n - 1, 0, -1): if s[:k] s[n - k:]: return s[:k] return 这段代码逻辑非常直白s[:k] 是前缀部分s[n-k:] 是后缀部分切片相等就说明找到了。从大到小试第一次命中的一定是最长的。我敢说这是绝大多数人拿到这题的第一版代码我也是这么写的写完一提交在大数据用例上超时了。2.2 复杂度吓人O(n²) 到底有多慢来分析一下为什么超时。最外层循环最多跑 n-1 次每次循环都要做一次字符串切片比较。Python 的字符串切片比较底层是逐字符比较的最多需要比较 k 个字符。所以最坏情况下总比较次数是(n-1) (n-2) ... 1 n(n-1)/2也就是 O(n²) 的时间复杂度。当 n 10^5 时这个数量级大约是 10^10 次字符比较Python 在 LeetCode 上每秒大概能跑 10^7 到 10^8 次简单操作10^10 意味着要跑几十秒甚至更久超时是必然的。C 也救不回来。就算用 std::string::substr 然后比较底层同样是逐字符比较复杂度依然是 O(n²)。这不是语言快慢能弥补的是算法设计的问题。2.3 小优化也救不回来有人会想那我从大到小找如果第一个就命中了不是很快吗这个思路理论上没错但题目数据可以专门构造一个最坏情况来卡你。比如 s aaaa...ab前面全是 a最后一个是 b。这时候前缀 aaa...a 和后缀 aaa...b 永远差最后一个字符只有 k 0 的时候才匹配但 k0 不在循环范围里。所以你从 n-1 一直试到 1每一次都要比较完整的前后缀全部失配稳稳吃满 O(n²)。这就是我老跟人说的暴力算法的时间复杂度是上限不是期望。测试数据不会指望你运气好它一定会构造让你运气最差的场景。想用暴力过这题基本没戏。3. 滚动哈希解法用数字指纹绕过字符串比较3.1 把字符串变成整数暴力法慢就慢在逐字符比较上。那能不能把字符串映射成一个整数比较数字 O(1) 就完成了这就是滚动哈希Rabin-Karp 算法的核心思想的出发点。做法是选一个基数 base把字符串当成一个 base 进制的数来处理。比如 s abc可以算hash ord(a) * base^2 ord(b) * base^1 ord(c) * base^0ord() 取字符的 ASCII 码。为了防溢出让 hash 对一个很大的质数取模。这样任何一个子串的哈希值我都能用前缀哈希数组 O(1) 算出来比较两个子串是否相同就变成比较两个整数是否相同从 O(k) 降到了 O(1)。3.2 前后缀哈希的计算细节思路很清晰预处理所有前缀的哈希值然后从大到小枚举长度 k计算前缀 s[:k] 的哈希值和后缀 s[n-k:] 的哈希值相等就返回。def longestPrefix(self, s: str) - str: n len(s) base, mod 131, 10**9 7 # 前缀哈希pre[i] 表示 s[:i] 的哈希值 pre [0] * (n 1) for i, ch in enumerate(s): pre[i 1] (pre[i] * base ord(ch)) % mod # 预计算 base 的幂 pow_base [1] * (n 1) for i in range(1, n 1): pow_base[i] pow_base[i - 1] * base % mod # 从长到短找 for k in range(n - 1, 0, -1): left pre[k] # 前缀 s[:k] 的哈希 right (pre[n] - pre[n - k] * pow_base[k]) % mod # 后缀 s[n-k:] 的哈希 if left right: return s[:k] return 这里唯一有点绕的是后缀哈希的公式。pre[n] 是整个字符串的哈希pre[n-k] 是去掉后 k 个字符后的前缀哈希。把 pre[n-k] 乘上 base^k相当于把它补齐到和 pre[n] 同样的位数然后相减剩下的部分就是 s[n-k:] 对应的哈希值。这个操作是老朋友了字符串哈希的经典推导。3.3 碰撞问题怎么看待滚动哈希看起来完美O(n) 的时间复杂度代码也不长。但它有一个理论上的瑕疵——哈希碰撞。两个不同的字符串哈希值理论上可能相等因为取模操作把无穷无尽的字符串压缩到了 mod 的有限空间里。虽然 10^97 这个质数很大碰撞概率极低但它不是 0。LeetCode 的评测用例是固定的不会专门构造哈希碰撞的数据来卡你所以单 mod 的写法在这道题上一般能过。但如果是面试现场面试官很可能会追问一句你这个比较在数学上严格吗你要是回答不上来印象分会打折扣。稳妥的做法之一是双 mod同时用两个不同的质数取模两个哈希值都相等才认为字符串相同碰撞概率直接降到几乎可以忽略。但这样做代码量翻倍而且本质上依然不是 100% 严格。字符串比较要做到算法上的绝对正确还是要回到 KMP 上。4. KMP 前缀函数最优解法与完整代码4.1 什么是前缀函数前缀函数是 KMP 算法的灵魂定义如下对于字符串 s前缀函数 pi[i] 表示子串 s[0..i] 的最长相等真前后缀的长度。说人话就是只看字符串从开头到第 i 个字符这一段它最长的那个 border 是多长。这个定义和快乐前缀是同一个东西吗几乎就是。区别只在于前缀函数是对 s 的每个前缀子串算 border 长度而快乐前缀只问整个字符串 s 的 border。所以这道题的核心洞察就是只要算出 pi[n-1]就能得到答案pi[n-1] 本身就是最长快乐前缀的长度。我用个不太严谨但好记的类比把字符串想象成一条拉链前缀和后缀就是拉链两端能咬合的部分。pi 数组记录的是每一段最多能咬合多少个齿而快乐前缀问的是整条拉链两端最多能咬合多少。4.2 递推计算的原理与实现前缀函数不是从零开始重新暴力匹配的它利用了一个很巧妙的递推假设我已经知道了 pi[i-1] j也就是说 s 的前 i 个字符的某个后缀和前 j 个字符完全相同。现在来了一个新字符 s[i]我要看它能不能让这个匹配延长一位。如果 s[i] s[j]那就太好了直接把 j 加 1 就是 pi[i]。如果 s[i] ! s[j]不能直接放弃。前面匹配好的 j 个字符里它本身也有更短的 border也就是 pi[j-1]。我把 j 退回到 pi[j-1]再看 s[i] 能不能接上新的 j。如果还不行继续退。这就是 while 循环在做的事。def longestPrefix(self, s: str) - str: n len(s) pi [0] * n for i in range(1, n): j pi[i - 1] while j 0 and s[i] ! s[j]: j pi[j - 1] if s[i] s[j]: j 1 pi[i] j return s[:pi[n - 1]]我自己第一次看这个递推的时候卡在 while 循环里好一阵。后来我给自己举了个例子s ababc算 pi[4] 的时候已知 pi[3] 2abab 的 border 是 ab新字符是 c而 s[2] ac 不等于 a所以 j 从 2 退到 pi[1] 0再看 s[4] 和 s[0] 比c 不等于 a所以 pi[4] 0。手动跑一遍就明白了回退不是回到上一次匹配位置而是回到当前匹配段内部的更短匹配这是 KMP 高效的核心。4.3 为什么 pi[n-1] 就是答案这里我见过不少刚学的人绕不过去pi 数组是给每个前缀算 border那答案不应该是 pi[pi[n-1]-1] 之类的东西吗不是。你把定义理一遍就清楚了。pi[n-1] 是整个字符串s 的最长 border 长度。而快乐前缀的定义就是整个字符串的最长真前后缀。两者定义完全重合所以 pi[n-1] 就是最长快乐前缀的长度。直接切片 s[:pi[n-1]] 就是答案。那 pi[pi[n-1]-1] 是什么它是最长 border 的 border也就是第二长的快乐前缀。如果题目改成找第二长快乐前缀才需要用到这一层。LeetCode 这道题只要最长的所以一行切片就完事了。4.4 时间复杂度为什么是 O(n)很多人看前缀函数那段 while 循环总觉得最坏情况下会退很多次复杂度会不会变成 O(n²)不会。关键在于变量 j 的变化规律每次循环 i 自增一次j 在 if 分支里最多加 1整个循环过程中j 的总增加量最多是 nwhile 里每次回退都会让 j 变小但 j 总共只有那么多本钱可退所以总回退次数不会超过 n所以整体的均摊复杂度是 O(n)。这个论证方式是 KMP 复杂度分析的标准套路能自己推一遍才算是真懂。另外空间复杂度 O(n)pi 数组占了主要部分。对于这道题来说这就是时空双优的最优解也是面试官最想看到的答案。5. 边界条件和典型坑位盘点5.1 几个典型用例的手算第一组s aaaa手动算 pipi[0] 0pi[1] 1aa 的 border 是 api[2] 2aaa 的 border 是 aapi[3] 3aaaa 的 border 是 aaa答案 s[:3] aaa。注意这里不是 aa而是 aaa。因为整个串去掉最后一个 a 后是 aaa它与 aaa 后缀完全相等。别凭直觉以为是一半边界是去掉最后一个字符不是取一半。第二组s abc所有前缀都不同所有后缀也都不同pi[2] 0返回空串 。题目要求在这种情况下返回空字符串不是返回 None。第三组s abababpi[0] 0pi[1] 0pi[2] 1aba 的 border 是 api[3] 2abab 的 border 是 abpi[4] 3ababa 的 border 是 abapi[5] 4ababab 的 border 是 abab答案 s[:4] abab和前面 1.2 手工枚举的结果一致。5.2 常见问题排查速查表问题原因解决办法返回了 a 而不是 s 长度为 1把 s 本身当成前后缀了记住 k 必须小于 npi[0] 始终是 0返回长度为 2 而不是 3aaaa 用例误以为边界是一半边界是去掉末尾字符不是对半分暴力代码大数据超时O(n²) 复杂度过高换滚动哈希或 KMP 前缀函数哈希代码在极端用例 WA单 mod 哈希碰撞换双 mod或直接用 KMP不理解 while 回退逻辑没搞清 pi[j-1] 的含义手动模拟 ababc 的 pi 计算返回值弄成长度没读题1392 要求返回子串不是长度这里我特别想强调一个坑LeetCode 的 1392 要求返回子串不是返回长度。很多新手做完同类型的求最长公共前后缀的长度题之后惯性思维直接把 pi[n-1] 当成返回值结果就错了。看题目输出示例l、abab 这种东西明显是字符串不是数字。6. 字符串 Hard 题的破题思路与心得6.1 识别border 型题目刷题多了你会发现LeetCode 上一大批字符串题的核心都在 border 这个概念上做文章重复子字符串问题判断字符串是否由某个子串重复构成就是看 n % (n - pi[n-1]) 0找出所有重复前缀后缀的题字符串周期性分析某些要求前缀与后缀匹配的题识别模型的方法很简单题目里同时出现了前缀和后缀这两个词并且要求它们相等那八成就是 border 问题。这时候不要急着写暴力先想想 KMP 前缀函数能不能直接套。这就像你看到二叉树的题先想递归一样是刷题直觉的一部分。6.2 现场面试怎么讲如果面试遇到这题我建议按这个顺序组织回答先给定义最长快乐前缀就是最长公共真前后缀在 KMP 里叫 border。然后说解法我们可以用前缀函数来算前缀函数 pi[i] 记录的是 s[0..i] 的最长 border 长度所以 pi[n-1] 直接就是答案的长度。接着讲复杂度O(n) 时间和 O(n) 空间这是最优解。最后面试官如果追问滚动哈希再补充说明哈希的碰撞风险和双 mod 方案。先把 KMP 讲清楚把为什么讲明白比急着写代码重要得多。我观察到很多候选人代码能写出来但说不清 while 回退的原理面试官一问复杂度为什么是 O(n)就卡壳了这样即便代码对评价也会打个折扣。6.3 个人刷题习惯与建议这道题我在自己整理字符串专题的时候把它归到了KMP 核心应用这一类里。我的习惯是每个专题选两三道代表性题目深入吃透而不是光看题解就划过去。1392 就是这种值得反复手算的题把 pi 数组从头到尾手动推几遍把 ababab、aaaa、abc 这些用例算明白KMP 的原理就再也忘不了。还有一个我后来才意识到的好处是理解透前缀函数之后再去做其他字符串题比如 LeetCode 热门的 28 题实现 strStr、459 题重复的子字符串都会觉得顺了很多。LeetCode 刷题指南里常有人纠结该刷多少道题我个人经验是同类型吃透三到五道比每种类型刷一道要有用得多。特别是字符串这种需要细节敏感的题材靠数量堆不出来靠的是把经典题的原理抠明白。