1. 为什么把三个算法放在一讲
最近在整理经典算法题精讲系列，这一讲比较特殊，把Manacher算法、bfprt算法、KMP算法放在了一起。乍一看这三个东西八竿子打不着——一个管回文串，一个管TopK，一个管字符串匹配。但把它们放一起讲是有道理的，因为它们共享同一个核心命题：如何把暴力解法优化到线性复杂度。
先从各自的战场说起。
KMP算法解决的是字符串匹配问题，就是在一个长文本里找一个模式串是否出现、出现在哪。暴力做法是拿模式串逐位对齐主串，失配就右移一位重新比较，最坏复杂度O(n*m)。KMP的精髓在于失配时不回退主串指针，只利用已匹配部分的信息快速移动模式串，把匹配过程压到O(n+m)。
Manacher算法解决的是最长回文子串问题。回文串是正着读倒着读都一样的字符串，比如"aba"、"abba"。暴力解法以每个字符为中心向两边扩展，复杂度O(n²)。Manacher利用回文的镜像对称性质，在扩展过程中复用已经算过的回文半径信息，把复杂度降到O(n)。
bfprt算法解决的是无序数组中找第K小（或第K大）元素的问题。常规思路是用快速排序的partition做随机选择，期望O(n)，但最坏退化到O(n²)。bfprt是一套确定性的选主元策略，保证每次partition都能淘汰足够多的元素，从数学上证明最坏也是O(n)。这五个字母来自Blum、Floyd、Pratt、Rivest、Tarjan五位作者的名字，所以也叫"中位数的中位数"算法。
这三个算法在面试和竞赛中的出场率很高，但很多人对它们的理解停留在"背模板"层面，换个场景就懵。比如KMP的next数组求法，江湖上有至少三种定义方式，网上教程各写各的，初学者很容易绕晕。比如Manacher的对称性优化，边界情况处理错一位整个结果就崩。再比如bfprt，问"为什么必须是5个一组"能答上来的人真不多，大多数只是机械地照着代码抄。
这篇是先讲KMP和Manacher，bfprt的完整版本放在下一篇展开。之所以这么安排，是因为KMP的next数组演示了"信息复用"这个思想的最基础形态，Manacher则在这个思想上加了一层"对称性"的巧劲，bfprt又把它延伸到"确定性选主元"的方向。三个算法放在一起看，能明显感受到算法优化的一条主线：想办法利用已有的计算结果，避免重复劳动。
下面先把KMP掰开揉碎讲清楚，再讲Manacher。整个过程我尽量用"当初我学的时候踩过的坑"的视角来写，配合完整的Java实现代码，最后附上刷题时常见的几个问题排查思路。
2. KMP算法：next数组是灵魂
2.1 从BF算法到KMP：到底优化了什么
先明确一点：KMP解决的是单模式串匹配问题。给定一个主串S和一个模式串P，要在S中找到P第一次出现的位置。最原始的做法叫BF算法（Brute Force），也叫朴素匹配。
BF的做法：从S的每个位置i出发，拿P逐位对齐比较。如果某一位失配，就把P整体右移一位，从P的第0位重新开始比较。
public static int bfSearch(String s, String p) { int n = s.length(), m = p.length(); for (int i = 0; i + m <= n; i++) { int j = 0; while (j < m && s.charAt(i + j) == p.charAt(j)) { j++; } if (j == m) { return i; } } return -1; }这段代码逻辑没错，问题出在效率上。假设S是"aaaaaaaaaaaaaaaaab"，P是"aaab"，每次都要比较到P的最后一位才发现失配，然后i只前进一位。整体下来近似比较nm次，复杂度O(nm)。
仔细想想，BF到底浪费了什么信息？答案是：已经匹配成功的那一段，被白白丢掉了。
举个例子，S="ababcabcabababd"，P="ababd"。当P的前4位"abab"都匹配成功，第5位P[4]='d'与主串中的'c'失配时，我们能从这个"4位已经匹配"的事实中推导出什么？P的前缀"abab"有长度为2的公共前后缀"ab"，这意味着如果把P右移2位，P的前缀"ab"依然能和主串当前位置之前的"ab"对上。这个结论只需要分析P自己就能得到，不需要知道主串的任何额外信息。
KMP的核心思想就用一句话概括：失配时，利用模式串自身的结构信息，把模式串一次性右移到可能匹配的最远位置，主串指针绝不回退。
这里的"模式串自身的结构信息"，就是next数组。
2.2 next数组的两种定义方式，别再混了
网上讲KMP的教程，next数组的定义有无数种版本，本质都是"最长公共前后缀长度"，但在具体实现上差一位。
先明确一个基础概念：对于一个字符串，它的前缀是去掉末尾若干字符后得到的子串，后缀是去掉开头若干字符后得到的子串。所谓"最长公共前后缀"，就是既是前缀又是后缀的最长子串长度，且这个子串不能是字符串本身，也不能是空串。
比如"ababa"：
- 长度为1的前后缀："a"和"a"，相等，匹配长度为1
- 长度为2的前后缀："ab"和"ba"，不等
- 长度为3的前后缀："aba"和"aba"，相等，匹配长度为3
- 长度为4的前后缀："abab"和"baba"，不等
所以"ababa"的最长公共前后缀长度是3。
网上常见的next数组定义有两种：
定义A：next[i]表示模式串P的[0, i)子串（即P[0..i-1]）的最长公共前后缀长度，也就是中文教程里常说的"前缀函数"。这里的next[0]=-1（有些约定为0），表示空串没有公共前后缀。
定义B：next[i]表示模式串P的[0, i]子串（即P[0..i]）的最长公共前后缀长度，即next[i]对应的是包含第i个字符在内的子串。
两种定义各有拥护者，计算出来的next数组整体错一位，但匹配时的跳转逻辑也相应调整。KMP本身没有歧义，算法是正确的，歧义全在next数组的具体约定上。
这篇文章里，我采用题目中给出的定义来规定：next[i]定义为模式串p[0..i-1]的最长公共前后缀长度，不过next[0]我习惯设为-1，用-1作为"公共前后缀不存在"的哨兵。
为了避免歧义，下面直接用具体例子说明。
2.3 手算abacaba的next数组
看题目里的例子：模式串P="abacaba"，按照next[i]定义为p[0..i-1]的最长公共前后缀长度来计算。
先拆开看每个前缀子串：
i=0: 空串，next[0] = -1 i=1: p[0]="a"，最长公共前后缀长度为0，next[1] = 0 i=2: p[0..1]="ab"，前缀"a"后缀"b"不等，next[2] = 0 i=3: p[0..2]="aba"，前缀"a"=后缀"a"长度1，更长的不行，next[3] = 1 i=4: p[0..3]="abac"，"a"和"c"不等，next[4] = 0 i=5: p[0..4]="abaca"，前缀"a"=后缀"a"长度1，前缀"ab"和后缀"ca"不等，next[5] = 1 i=6: p[0..5]="abacab"，前缀"ab"=后缀"ab"长度2，"aba"和"cab"不等，next[6] = 2 i=7: p[0..6]="abacaba"，前缀"aba"=后缀"aba"长度3，next[7] = 3所以得到：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| next[i] | -1 | 0 | 0 | 1 | 0 | 1 | 2 | 3 |
这里的next[7]是最后用到的值吗？不一定。如果匹配到P最后一位失败了，需要跳转到next[7]=3，也就是说明"前7位都匹配上了，但第8位失配，此时模式串最长公共前后缀长度为3，所以从下标3继续尝试"。
理解这个表之后，再来看代码实现。
求next数组的代码，经典写法如下：
public static int[] getNext(String p) { int m = p.length(); int[] next = new int[m + 1]; next[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || p.charAt(i) == p.charAt(j)) { i++; j++; next[i] = j; } else { j = next[j]; } } return next; }这段代码的核心逻辑是：用两个指针i和j，j代表"已经匹配上的公共前后缀长度"。如果p[i]==p[j]，说明公共前后缀可以延长一位，继续；如果失配，j就回退到next[j]，相当于在计算next数组的过程中也要用到next数组自身的跳转信息，这就是"递归地利用已计算的信息"。
有个细节值得注意：next数组长度是m+1而不是m，因为按照定义A，next[m]是完整的P[0..m-1]的最长公共前后缀长度，匹配过程中模式串走到头时也要查这个值。
2.4 KMP匹配过程：主串指针不回退
有了next数组，匹配逻辑就顺理成章了。
public static int kmpSearch(String s, String p) { int n = s.length(), m = p.length(); if (m == 0) return 0; int[] next = getNext(p); int i = 0, j = 0; while (i < n) { if (j == -1 || s.charAt(i) == p.charAt(j)) { i++; j++; } else { j = next[j]; } if (j == m) { return i - m; } } return -1; }匹配时最关键的跳转分支是else：当s[i] != p[j]时，主串下标i不动，只把模式串下标j更新为next[j]。这里next[j]的含义是"前j个字符已经匹配相同时，最长公共前后缀的长度"，所以模式串跳到该长度处继续比较，而主串当前位置之前的那些字符已经保证与模式串前缀对齐了。
用生活类比理解：你在书里查找一个词，当连续几页都符合关键词前缀，突然某一页对不上时，你不会回到书的第一页重查，而是根据已经匹配到的部分，把关键词的某个前缀对齐到当前页，继续往后翻。主串就好比书页，只有前进没有后退；模式串的移动靠next数组来指导。
来看一个具体的匹配例子。主串S="ababacabacaba"，模式串P="abacaba"。
- i=0，j=0，s[0]='a'与p[0]='a'匹配，i=1，j=1
- i=1，j=1，s[1]='b'与p[1]='b'匹配，i=2，j=2
- i=2，j=2，s[2]='a'与p[2]='a'匹配，i=3，j=3
- i=3，j=3，s[3]='b'与p[3]='c'失配，j跳到next[3]=1，主串不前进
- i=3，j=1，s[3]='b'与p[1]='b'匹配，i=4，j=2
- i=4，j=2，s[4]='a'与p[2]='a'匹配，i=5，j=3
- i=5，j=3，s[5]='c'与p[3]='c'匹配，i=6，j=4
- i=6，j=4，s[6]='a'与p[4]='a'匹配，i=7，j=5
- i=7，j=5，s[7]='b'与p[5]='b'匹配，i=8，j=6
- i=8，j=6，s[8]='a'与p[6]='a'匹配，i=9，j=7，j==m，返回i-m=2
主串从位置2开始匹配成功，即子串"abacaba"出现在S[2..8]位置。
注意在第4步，主串index=3处的失配，i没有回退到1，而是原地等待模式串通过next跳转后继续比较。这就是KMP主串不回退的直观体现。
KMP的时间复杂度为什么是O(n+m)？匹配过程中i只会增加不会减少，最多增加n次；j每次失配时通过next跳转会变小，但j增加的次数不超过i增加的次数（每次匹配成功j加1，匹配失败j减少但总量有限），整体均摊下来代价是线性的。求next数组同理，i和j的移动次数也是O(m)。所以最终是O(n+m)。
2.5 KMP的应用远不止字符串匹配
很多初学者觉得KMP只能用来做文本里的子串查找，其实它的应用面比想象中宽。
第一个实用场景是判断一个字符串是否是另一个字符串的循环移位。比如判断B是否是A的循环移位，常规思路是A+A拼起来，看B在A+A中是否出现。这本质就是一次KMP匹配。
第二个场景是求字符串的最短重复周期。给一个字符串s，如果它可以由某个子串重复k次构成，找出这个最小周期子串。结论是用KMP求出next数组后，答案是n - next[n]，如果n % (n - next[n]) == 0，那么这个最短重复周期长度就是n - next[n]。这个结论在很多字符串题里是隐藏考点。
第三个场景是KMP自动机思想。把KMP的匹配过程理解成"模式串在不同状态之间跳转"，这就是有限状态自动机的雏形。AC自动机（多模式串匹配）、最大长度前缀匹配等进阶算法都建立在这个思想上。所以说KMP不是孤立的一个小技巧，它是很多字符串数据结构的底层地基。
提示：刷题时如果遇到"判断子串是否出现""求最短周期""循环移位"这类描述，第一反应应该是KMP或KMP的变形，而不是直接上暴力。
3. Manacher算法：最长回文子串的线性解法
3.1 回文问题的暴力解法为什么慢
KMP讲清楚了，来看Manacher。这个算法解决的是最长回文子串问题，比如给定字符串"babad"，最长回文子串是"bab"或"aba"（长度3）。
暴力解法有两种思路。第一种是枚举所有子串，逐个判断是否回文，复杂度O(n³)，基本属于不可用。第二种是中心扩展法：枚举每个位置作为回文中心，向两边扩展直到不能扩展为止，记录最长的回文长度。
public static String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, maxLen = 1; for (int i = 0; i < s.length(); i++) { int len1 = expand(s, i, i); // 奇数长度回文 int len2 = expand(s, i, i + 1); // 偶数长度回文 int len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substring(start, start + maxLen); } private static int expand(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1; }中心扩展法的时间复杂度是O(n²)，在字符串长度几百万级别时完全跑不动。Manacher算法的目标是把复杂度压到O(n)。
它的核心优化只有一条：当我们要计算某个位置的回文半径时，如果这个位置位于之前某个大回文的内部，那么可以利用回文的对称性，直接借用对称位置的已知回文半径作为初始值，省去从1开始扩展的过程。
3.2 镜像对称：Manacher最巧妙的优化
要理解Manacher，先弄明白四个变量：
- C：当前已知的回文串的中心位置
- R：当前已知的回文串的最右边界（R右边那个位置，表示半径覆盖到R-1）
- P[i]：以位置i为中心的回文半径（包含中心本身）
- mirror = 2*C - i：i关于C的对称位置
算法的核心逻辑是：如果i在R的范围内，即i < R，那么P[i]至少等于min(P[mirror], R - i)。
为什么？因为i和mirror关于C对称，而C的回文范围[R的左边界, R]是对称的。既然以C为中心的回文包含了i和mirror，那么mirror回文半径里的内容，在i的镜像位置上一定也是对称的。所以P[i]可以直接从P[mirror]继承，这是Manacher的加速核心。
但有个限制条件：P[i]不能超过R-i，因为一旦超过R，就超出了C的回文覆盖范围，这个范围之外的对称性就无法保证了。所以取min(P[mirror], R - i)。
如果i在R之外，没有对称信息可用，P[i]初始为1。
这里有一个关键问题：回文半径的奇偶性怎么处理？
回文串有两种情况：奇数长度如"aba"中心是单个字符"b"；偶数长度如"abba"中心在"bb"之间。直接处理时，需要区分两种情况，代码写起来麻烦，而且P数组在不同情况下含义不一致。Manacher的经典做法是在原始字符串的每个字符之间（包括首尾）插入一个特殊字符，比如把"aba"改写成"#a#b#a#"，把"abba"改写成"#a#b#b#a#"。
插入后，原来的奇数回文和偶数回文都统一成了奇数回文（以特殊字符为中心或普通字符为中心），处理起来就不需要分支判断了。这里的特殊字符可以是任何不冲突的字符，比如'#'，因为它不会与原始字符匹配。
原始字符串s长度为n，变换后的字符串t长度为2n+1。求得的P[i]是t中以i为中心的回文半径，对应到原始字符串的回文长度就是P[i]-1。最终答案就是所有P[i]中的最大值减1。
3.3 Manacher的完整实现与边界分析
直接看代码：
public static String manacher(String s) { if (s == null || s.length() == 0) return ""; // 构造带分隔符的字符串 char[] chars = new char[s.length() * 2 + 1]; int idx = 0; for (int i = 0; i < chars.length; i++) { chars[i] = (i % 2 == 0) ? '#' : s.charAt(idx++); } int n = chars.length; int[] p = new int[n]; int C = 0, R = 0; int maxLen = 0, maxCenter = 0; for (int i = 0; i < n; i++) { // 利用对称性初始化 p[i] if (i < R) { int mirror = 2 * C - i; p[i] = Math.min(p[mirror], R - i); } else { p[i] = 1; } // 中心扩展 while (i - p[i] >= 0 && i + p[i] < n && chars[i - p[i]] == chars[i + p[i]]) { p[i]++; } // 更新 C 和 R if (i + p[i] > R) { C = i; R = i + p[i]; } // 记录最大长度 if (p[i] - 1 > maxLen) { maxLen = p[i] - 1; maxCenter = i; } } // 根据中心位置还原原始字符串 int start = (maxCenter - maxLen) / 2; return s.substring(start, start + maxLen); }逐行拆解：
第一步构造带分隔符的数组。偶数位放'#'，奇数位放原始字符，注意chars[1]是s[0]，chars[3]是s[1]，以此类推。
第二步初始化P[i]。当i < R时，用对称性预填一个初始值，这样while循环的扩展次数被大大压缩。当i >= R时，没有对称信息可用，初始为1。
第三步中心扩展。这个while循环看起来和暴力中心扩展一样，但它的执行次数已经被前面的初始化大幅削减。注意边界条件：i - p[i] >= 0 和 i + p[i] < n，防止数组越界。
第四步更新C和R。C和R的更新原则是：一旦发现当前位置的最右边界超过了原来的R，就更新R和C。这保证了后续位置尽量多的i能够落在R的范围内，从而利用镜像优化。
第五步记录最大长度。maxLen = p[i] - 1，对应原始字符串的回文长度。
还原原始字符串的下标时有一个小技巧：maxCenter是变换后数组中的中心下标，maxLen是原始回文长度，那么原始字符串起始位置是(maxCenter - maxLen) / 2。这个公式可以自己推一下：变换后的字符到原始字符的下标映射关系是rawIndex = transformedIndex / 2（因为插入字符占了一半位置），回文在变换后数组中的区间是[maxCenter - maxLen, maxCenter + maxLen]，除2后对应的原始区间起点就是(maxCenter - maxLen) / 2。
3.4 复杂度分析和几个容易踩的坑
Manacher的复杂度为什么是O(n)？看似while循环里有一层嵌套，但是注意：每次while扩展都会使R向右移动，而R在整个算法过程中只会向右移动，最多移动n次。所以while循环的总执行次数是O(n)的。P数组的初始化、C和R的更新都是O(1)操作，总的循环次数n次，所以整体是O(n)。
实际操作中有几个坑，我在这里集中说一下：
第一个坑是分隔符的选择。用'#'是惯例，但要求这个字符不能出现在原始字符串里，否则会干扰匹配。比如原始字符串里有'#'，你还用'#'做分隔符，整个算法的正确性就被破坏了。稳妥做法是选一个不影响判断的字符，或者明确知道原始字符集范围。
第二个坑是P[i]的初始值。我见过很多人把p[i]初始化写成0，然后while循环里从i开始扩展，这样就会漏掉单个字符的回文情况，导致边界问题。记住p[i]至少是1，因为单个字符本身是回文。
第三个坑是还原原始字符串下标时容易算错。直接用原始思路推导会快很多，别死记公式，推一遍就懂。
第四个坑是C和R的更新时机。只有当i + p[i] > R时才更新，等于不更新。因为等于的时候，新的回文半径没有超出已有覆盖范围，不需要调整。
注意：Manacher求的是最长回文子串的长度或者具体子串。如果题目只需要长度，可以精简掉字符串还原部分，只保留maxLen的计算。
Manacher在高频面试题中的出现率很高，尤其是字节、快手的算法题库里，"最长回文子串"几乎是标配题，用Manacher写成O(n)级别，面试官的印象分会比O(n²)高不少。
4. bfprt算法：确定性搞定TopK问题
4.1 TopK问题为什么难在"最坏情况"
前两个算法都讲完了，最后说bfprt。整体安排在下一篇展开，但核心思路和代码框架值得先在这里铺垫一下，方便大家把三个算法串起来理解。
问题定义：给定一个无序数组，找出第K小（或第K大）的元素。比如[3, 2, 1, 5, 6, 4]，K=2时答案是2（排序后为[1,2,3,4,5,6]，第2小是2）。
最简单的做法是排序后取第K个，复杂度O(n log n)。但这个问题比排序更简单，不需要完全有序，所以期望做到O(n)。
常见的优化方案是快速选择（QuickSelect）：利用快速排序的partition思想，每次选取一个pivot，把数组分成小于pivot和大于pivot两部分。如果pivot的位置恰好是K，直接返回；否则在左半边或右半边递归。随机选pivot时，期望复杂度是O(n)，但最坏情况下每次选到最大（或最小）元素，递归规模每次只减少1，复杂度退化为O(n²)。
bfprt算法要解决的就是这个最坏情况，它通过一种确定性的pivot选择策略，保证无论输入数据长什么样，复杂度都能控制在O(n)。
4.2 中位数的中位数：五个一组的原因
bfprt的核心是"中位数的中位数"选主元思路，整个过程分五步：
- 将数组按每5个元素一组分组，最后一组不足5个也单独成组
- 对每组内的元素排序（组内最多5个，用插入排序即可）
- 取出每组的中位数，放到一个新的数组中
- 递归调用bfprt求这个中位数数组的中位数，把它作为pivot
- 用pivot对原数组做partition，根据partition后的位置判断是在左边找还是在右边找，递归处理
为什么必须是5个一组？这是bfprt算法中最核心的证明点。
假设数组有n个元素，5个一组共有n/5组（近似）。每组内部排序后取中位数，由于每组有5个元素，中位数是第3个（即每组有2个元素小于等于该组中位数，2个元素大于等于）。这些中位数的中位数记为pivot。那么有多少元素能确定小于pivot？
有一半的组的中位数小于等于pivot（因为pivot是中位数的中位数），这些组各有2个元素小于等于该组中位数，所以这些组的至少3个元素小于等于pivot（该组中位数本身加上2个更小的）。粗略估算有约(n/10)*3 = 3n/10个元素一定小于pivot。同理，约3n/10个元素一定大于pivot。所以partition之后，最坏情况下递归处理的子问题规模不超过7n/10。
由此得到递归式：T(n) ≤ T(n/5) + T(7n/10) + O(n)，其中T(n/5)是求中位数的中位数的时间，T(7n/10)是递归查找的时间，O(n)是分组、排序、partition的时间。解这个递归式，最终得到T(n) = O(n)。用替代法可以直接证明。
为什么不用3个一组？3个一组的话，每组中位数以上的元素有2个，有一半组的中位数小于pivot，所以能确定小于pivot的元素约(n/6)*2 = n/3，递归规模变为2n/3，递归式变为T(n) ≤ T(n/3) + T(2n/3) + O(n)，这个式子解出来是O(n log n)，无法保证线性。7个一组可以，但分组排序的常数更大，实际运行更慢。5个一组是数学证明和工程效率的平衡点。
4.3 bfprt的确定性为什么重要
bfprt相对QuickSelect的优势是"确定性"。QuickSelect依赖随机性，虽然期望复杂度是O(n)，但在某些特定输入下（比如数组已经有序且每次pivot都选到最小值）会退化。bfprt不依赖数据分布，无论输入什么，都能保证O(n)。
但是这里要说不中听的话：bfprt的常数特别大，每次递归都要分组、组内排序、求中位数数组的中位数，实际运行时间可能比QuickSelect慢好几倍。所以它在工程中很少直接使用，更多是作为理论工具出现。比如在算法课上证明"选择问题存在确定性线性算法"，或者在某些实时系统里要求最坏情况可控的场景。
面试中如果被问到，建议这样回答：先说bfprt是确定性O(n)的TopK算法，再说五步流程，最后强调5个一组的原因——保证每次partition至少删除3n/10个元素，递归规模最多7n/10，最终解出O(n)。
完整代码实现、变种问题和复杂度的严格数学证明，我放在下一篇写。这里先给出一个简单的Java框架，方便对照理解：
public static int bfprt(int[] arr, int k) { // k从1开始计数 return bfprt(arr, 0, arr.length - 1, k - 1); } private static int bfprt(int[] arr, int left, int right, int k) { if (left == right) return arr[left]; int pivot = medianOfMedians(arr, left, right); int[] range = partition(arr, left, right, pivot); if (k >= range[0] && k <= range[1]) { return arr[k]; } else if (k < range[0]) { return bfprt(arr, left, range[0] - 1, k); } else { return bfprt(arr, range[1] + 1, right, k); } }这里的medianOfMedians对应上面说的选主元逻辑，partition是荷兰国旗问题的三路快排写法。等下篇再展开。
5. 常见问题与排查技巧实录
5.1 KMP next数组求错的排查思路
KMP写出来跑一遍结果不对，90%的情况是next数组求错了。排查时按以下步骤走：
第一步，对照你采用的next定义，手算几个简单串的结果，比如"aaaa"、"abab"、"abcabc"，看看你的代码输出是什么。如果手算和代码不一致，说明理解或实现有一方出了问题。
第二步，重点检查求next的循环边界。while循环的终止条件、i和j的初始值、next[i]赋值时机，这三处最容易错。比如忘了next[0]=-1，或者在失配时回退j写成j--而不是j=next[j]，都会导致结果偏差。
第三步，打印匹配过程的中间变量。在kmpSearch的else分支里打印i和j的值，观察主串指针是否真的没有回退，模式串跳转是否和手算一致。
我见过一个典型错误：定义A和定义B混用。求next时用定义A（next[i]=p[0..i-1]的最长公共前后缀），但匹配跳转时却按定义B的逻辑来。虽然只是差一位，但最终的匹配结果完全不对。
5.2 Manacher边界问题排查
Manacher代码不长，但边界问题非常隐蔽。如果你发现结果差一位，或者偶数字符串处理错，先检查以下几点：
第一，检查构造的变换数组是否正确。下标0放'#'，下标1放s[0]，下标3放s[1]，这个映射错了整个算法全崩。可以先打印变换后的字符数组，肉眼核对。
第二，检查while循环的边界条件。i - p[i] >= 0和i + p[i] < n这两个条件缺一不可，少写一个就会数组越界。
第三，检查还原回文子串的公式。之前提到start = (maxCenter - maxLen) / 2，这里maxCenter是变换后数组的下标，maxLen是原始回文长度。如果你用p[i]直接当作原始长度，还原出的字符串就是错的。
第四，检查空串和单字符的边界情况。空串直接返回空，单字符返回自身，这两个case要单独处理。
5.3 面试中的常见追问与应对思路
这三个算法在面试中只会写代码是不够的，很可能被追问到原理层面的问题。
对于KMP，面试官最常问的是：next数组怎么来的？为什么时间复杂度是O(n)？next[j]回退时为什么不会漏掉可能的匹配？回答时抓住"主串指针不回退"和"利用模式串自身的最长公共前后缀信息"这两个核心就行。
对于Manacher，高频追问是：为什么插入分隔符后能统一奇偶？为什么P[i]的初始值取min(P[mirror], R-i)？复杂度的直观解释是什么？回答时记得强调"超过R的部分对称性无法保证，所以必须取min"这个关键点。
对于bfprt，高频追问是：为什么是5个一组？3个一组行不行？怎么证明复杂度是O(n)？回答时把递归式和分组淘汰比例讲清楚，基本就能过。
还有一个小技巧：面试时如果写了bfprt，可以先说一句"这个算法常数比较大，实际工程中通常用随机化QuickSelect，但bfprt的优势是确定性O(n)"。这句话能体现你对算法有整体认知，而不仅仅是背了模板。
6. 三个算法的共同主线
把KMP、Manacher、bfprt放一起讲完，再回头看它们的联系。
KMP的next数组是"利用已匹配部分的公共前后缀信息"，避免主串回退；Manacher的P数组是"利用回文的镜像对称性"，避免重复扩展；bfprt是"分组取中位数，再取中位数的中位数"，避免partition选到极端pivot。三个算法从不同的角度验证了同一个道理：算法优化的本质是信息的最大化复用，以及最坏情况的主动规避。
这个道理应用到实际开发中，很多性能问题都能找到优化思路。比如处理字符串时，如果发现某些子串被反复计算，就要考虑预处理+记忆化；处理大数据时，如果某种选主元策略在极端输入下会退化，就要考虑更稳妥的确定性策略。
下一篇会展开bfprt的完整实现，包括每组排序代码、中位数数组的递归处理、partition的三路划分，以及几个变种题目（第K大、找中位数、找出所有TopK元素）的解法。到时候拿到代码，建议先自己跑一遍，再试着改一改，比单纯看一遍印象深得多。
我自己带过的学员里，很多人卡在这三个算法上是因为"眼高手低"——看讲解都觉得懂了，一写代码就各种边界问题。所以这里多说一句：算法这东西，看一百遍不如手写五遍，写完再对着测试用例跑，尤其要把刚才说的边界情况全部测一遍。这个过程不是浪费时间，而是真正把"别人的解法"变成"自己的内功"。
