企业官网建设流程全解析

Manacher算法、bfprt算法、KMP算法，这三个名字放在一起，乍看像是三道互不相干的算法题：一个管最长回文子串，一个管无序数组第K小，一个管字符串匹配。但刷久了你就会发现，它们其实是同一类东西——都是利用“已经算过的信息”去加速“后面的计算”，区别只在于各自存的“状态”不同。这篇文章我就把这三个算法的原理、代码、细节坑一次性讲透，适合准备算法面试、或者学完基础数据结构想进阶的读者。KMP部分我会重点拆解next数组的两种常见定义，Manacher会讲清楚回文半径数组为什么能镜像继承，BFPRT则会从快排partition的退化说起，把“为什么是5个一组”这件事讲明白。

1. 开题：这三个算法到底在解决什么难题

1.1 字符串匹配与模式串的自我重复

KMP解决的是“在一个长文本里找模式串”的问题，比如在主串ababcababac里找模式串ababac。暴力做法是枚举主串每个起点，然后逐位匹配，失败就把起点往后挪一位，最坏时间复杂度O(n*m)，n和m分别是主串和模式串长度。

但暴力做法有个明显的浪费：当主串匹配到第5位时，前4位都已经确认和模式串相同了，这时候失配，说明什么？说明这段主串的已知信息完全可以用来指导下一次匹配。KMP的核心思想就是，失配时不是让i回退，而是让模式串的指针j根据“模式串自身的重复结构”跳到一个合理位置。这个“重复结构”就是next数组，也叫前缀函数。

所以KMP的难点不在匹配过程本身，而在next数组的构造。你可以把next数组理解为“模式串自己的KMP匹配”：用模式串匹配模式串自己，找出每个位置之前的最长相同前后缀。

1.2 最长回文子串的暴力困境

Manacher算法解决的是“给定一个字符串，找出最长回文子串的长度或具体子串”。

暴力做法有两种：一种是枚举所有子串再判断回文，O(n^3)；另一种是枚举每个中心向两边扩散，O(n^2)。中心扩散其实已经很直观了，但问题在于它没有利用已经得到的回文信息。

举个实际例子，字符串abacaba，以中间的c为中心能扩散出整串回文，但如果让算法从头到尾老老实实每个中心都扩散一遍，很多中心其实已经被更靠左的回文覆盖过了。Manacher的突破点就在于：维护一个当前最右回文边界R和它的中心C，对于边界内的位置i，可以通过对称点i‘的回文半径直接初始化——这个“直接初始化”就是核心加速，它把每个位置的扩散基数从0变成了可能已经很大的值，整体复杂度降到O(n)。

1.3 TopK问题的确定性解法

BFPRT算法解决的是“在无序数组中找到第K小（或第K大）元素”的问题，也叫中位数的中位数算法（Median of Medians）。

常规思路是借助快速排序的partition函数，每次用随机或者固定基准把数组分成两半，然后根据基准位置决定走左边还是右边。平均复杂度是O(n)，但最坏情况会退化到O(n^2)，典型例子是数组已经有序且每次选到开头元素做基准。

BFPRT的意义在于：它给出一条确定性的路径，保证每次选出的基准都落在数组的30%到70%区间内，从而保证最坏时间复杂度也是O(n)。虽然常数较大，工程上通常不如随机选择或堆方案实用，但它提供了“确定性线性时间选择”的经典理论框架，面试里讲清楚它非常加分。

1.4 三个算法的共同气质

这三个算法表面上毫无关联，但你拆开看会发现它们的骨架惊人相似：

• KMP：模式串失配时，利用next数组（前缀函数）跳过不可能匹配的位置；
• Manacher：回文扩散时，利用对称性跳过已经确定回文的位置；
• BFPRT：递归选择时，利用中位数的中位数作为基准，缩小问题规模。

它们都包含一个“预处理结构”（next数组、回文半径数组、中位数数组），这个结构本质上是在回答一个问题：当我走到某一步时，哪些信息是已经知道的，可以直接拿来用？

理解了这层共同逻辑，学这三个算法就不会觉得是在背模板了。

2. KMP：next数组的本质是“用模式串匹配模式串”

2.1 从暴力匹配到前缀函数的跃迁

先看一段最朴素的暴力匹配：

for (int i = 0; i <= n - m; i++) { int j = 0; while (j < m && text.charAt(i + j) == pattern.charAt(j)) { j++; } if (j == m) return i; }

主串指针i + j每次失配要回退到i + 1，模式串指针j归零。这个回退动作是最浪费的。

KMP的优化思路是：主串指针只往前走，失配时只移动模式串。比如主串是abcabcabcd，模式串是abcabcd，匹配到第6位时失配（主串最后一位是d，模式串第6位是d？我换个例子：主串abcabcabx，模式串abcabx，匹配到第5位时，模式串的x和主串的a不匹配），这时候暴力做法是主串回到第2位重新开始。

但我们已经知道前面5位主串和模式串完全一样，等于知道这段内容是abcab。而abcab的后缀ab同时也是模式串的前缀，所以下一次可以直接用模式串的第3个字符c去跟当前主串位置比较。这就是next数组的作用：告诉你“失配之后，模式串指针该跳到哪个位置”。

2.2 手算 abacaba 的 next 数组

这里要先把定义说清楚，因为网上两种口径经常混用，很多人的困惑就在这里。

我采用的是源码里最常见的实现口径：定义next[i]为“模式串第 i 位失配时，j 应该回退到的位置”，它等于pattern[0..i-1]的最长相等真前后缀长度。特殊地，next[0] = -1。

以模式串abacaba为例，逐个推导：

• next[0] = -1，第0位失配时没有退路，j置为-1表示主串前进；
• next[1]：看pattern[0..0]，即a，它的真前后缀最长公共长度为0，所以next[1]=0；
• next[2]：看pattern[0..1]，即ab，前缀a和后缀b不相等，所以next[2]=0；
• next[3]：看pattern[0..2]，即aba，最长相等真前后缀是a，长度1，所以next[3]=1；
• next[4]：看pattern[0..3]，即abac，前缀a/ab/aba，后缀c/ac/bac，没有相等的，所以next[4]=0；
• next[5]：看pattern[0..4]，即abaca，相等的前后缀是a，长度1，所以next[5]=1；
• next[6]：看pattern[0..5]，即abacab，最长相等前后缀是ab，长度2，所以next[6]=2。

最终得到：

next = [-1, 0, 0, 1, 0, 1, 2]

注意最后一项只看到pattern[0..5]，也就是abacab，对应的是第6位失配时跳转的位置。很多刚学的人会直接看整个串abacaba的前后缀，算出3，然后和代码跑出的2对不上，原因就是这个口径差异。

如果某本教材用的定义是“next[i]表示pattern[0..i]的最长相等真前后缀长度”，那结果就是[-1, 0, 1, 0, 1, 2, 3]。不是说谁错了，而是它们对应的匹配代码写法不同。面试时建议先跟面试官确认口径，或者直接用我下面给的实现版本，代码和数组定义严格对应。

2.3 匹配阶段：主串不动，只回退模式串

拿到next数组后，匹配过程就很简单了：

int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || text.charAt(i) == pattern.charAt(j)) { i++; j++; } else { j = next[j]; } } if (j == m) return i - j;

注意j == -1这个分支。当next[j]被跳到-1时，说明连模式串第0位都匹配不上，这时候主串指针前进，模式串回到0位重新开始。

我建议你第一次学的时候，拿上面abacaba的next数组，配合主串abacabx手推一遍匹配过程，感受一下“主串指针不后退”是怎样做到的。这一步比看十遍代码都有用。

2.4 Java实现与两个next定义坑

贴一个可直接运行的KMP实现：

public class KmpMatcher { public static int indexOf(String text, String pattern) { if (pattern == null || pattern.length() == 0) return 0; int n = text.length(); int m = pattern.length(); if (n < m) return -1; int[] next = buildNext(pattern); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || text.charAt(i) == pattern.charAt(j)) { i++; j++; } else { j = next[j]; } } return j == m ? i - j : -1; } private static int[] buildNext(String pattern) { int m = pattern.length(); int[] next = new int[m]; next[0] = -1; int i = 0, j = -1; while (i < m - 1) { if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) { i++; j++; next[i] = j; } else { j = next[j]; } } return next; } public static void main(String[] args) { String text = "abacababacaba"; String pattern = "abacaba"; System.out.println(indexOf(text, pattern)); } }

这里有个容易踩的坑：构建next数组时，每次i++之后再赋值next[i] = j，意味着next[1]存的是pattern[0..0]的信息，next[i]总是滞后一位。所以前面手算abacaba时next最后一位是2而不是3。如果你在调试中打印next数组并拿“整个串的最长相等前后缀”去对照，肯定会觉得奇怪，其实只是数组的下标语义不同。

另一个坑是有人习惯把next数组整体加1，变成[0, 1, 1, 2, 1, 2, 3]，表示“模式串第几位失配时从几位开始比较”。两种写法本质完全一样，但千万别混着用：用加1版时注意失配回退是j = next[j] - 1还是直接j = next[j]，我在面试现场见过有人把两种写法揉在一起，代码直接越界。

3. Manacher：用镜像对称把回文半径“抄”过来

3.1 预处理：用占位符统一奇偶回文

回文分两种：奇数长度如aba，偶数长度如abba。暴力中心扩散需要分别处理，因为奇数回文的中心是一个字符，偶数回文的中心是两个字符之间。

Manacher的预处理思路很巧妙：在字符串每个字符之间以及首尾都插入一个不会出现的特殊符号，比如#：

原串: a b a 处理后: ^ # a # b # a $

我在实现时最外层还加了^和$两个哨兵，是为了在while扩散时免去越界判断。处理后的字符串长度变为2n+3，原来的奇数回文和偶数回文在预处理串里都变成了奇数回文，中心都是某个#或真实字符。统一成奇数以后，处理逻辑就只剩一种。

这里有一个换算关系很重要：预处理串里的回文半径减去1，正好等于原串的回文长度。比如原串aba，以b为中心的回文半径在预处理串里是4（从b到左边#、右边#都算上），4减1等于3，正好是aba的长度。这个关系网上很多文章不写清楚，导致你就算跑通了代码也不知道为什么返回的是max(p) - 1还是max(p)。

3.2 回文半径数组p[i]与最右边界right

Manacher维护两个关键变量：

• center：当前能覆盖到最右边界right的回文串中心；
• right：这个回文串的右边界下标。

对于当前位置i：

• 如果i在right左侧，说明i被某个回文串覆盖，可以找到它关于center的对称点mirror = 2 * center - i。由于回文串的对称性，mirror的回文半径在大部分情况下可以直接“抄”给p[i]；
• 如果i在right右侧或等于right，说明没有任何已知信息可以利用，只能老老实实从p[i]=0或p[i]=1开始扩散。

这个“抄”就是Manacher算法的加速核心。从直观上讲，你站在位置i，看到左边的对称位置mirror已经算出很大的回文半径，因为整个区间[center - right, center + right]是回文的，所以镜像位置的回文半径在超出right之前一定也成立。这就像照镜子，镜子里你的右边伸到哪里，你的左边在镜像空间里也能伸到哪里。

3.3 三类情况的分类讨论

具体分三种情况：

第一种，i在right右侧：没有信息可用，p[i]初始化为0，然后while扩散。

第二种，i在right左侧，且mirror的回文半径完全落在已知回文区间内：此时p[i] = p[mirror]，不需要扩散。

第三种，i在right左侧，但mirror的回文半径超出了已知回文区间的左边界：此时只能保证p[i]至少是right - i，超出部分需要while继续扩散验证。

这三种情况在代码里其实可以合并成一句：

p[i] = i < right ? Math.min(right - i, p[2 * center - i]) : 0;

然后无论哪种情况，都统一执行while扩散。因为如果可以直接继承的话，while判断会立即失败，不会影响结果。这样写代码非常简洁，但理解时要能区分三种情况，否则很难记住为什么用Math.min。

有一个关键点：right - i和p[mirror]取最小值，是因为镜像点的回文串如果超出了当前已知回文区间，超出部分不能保证对称相等，只能保守地初始化到right - i，剩余部分再验证。

3.4 Java实现与索引换算

直接上代码：

public class Manacher { public static int longestPalindromeLength(String s) { if (s == null || s.length() == 0) return 0; char[] t = preprocess(s); int n = t.length; int[] p = new int[n]; int center = 0, right = 0; for (int i = 1; i < n - 1; i++) { int mirror = 2 * center - i; p[i] = i < right ? Math.min(right - i, p[mirror]) : 0; while (t[i + p[i] + 1] == t[i - p[i] - 1]) { p[i]++; } if (i + p[i] > right) { center = i; right = i + p[i]; } } int maxLen = 0; for (int r : p) { maxLen = Math.max(maxLen, r); } return maxLen; } private static char[] preprocess(String s) { int n = s.length(); char[] t = new char[2 * n + 3]; t[0] = '^'; for (int i = 0; i < n; i++) { t[2 * i + 1] = '#'; t[2 * i + 2] = s.charAt(i); } t[2 * n + 1] = '#'; t[2 * n + 2] = '$'; return t; } public static void main(String[] args) { System.out.println(longestPalindromeLength("abacaba")); // 7 System.out.println(longestPalindromeLength("abbc")); // 2 } }

关于索引换算，还记得前面说的规律：p[i]减去1就是原串以该位置为中心的最长回文长度。为什么？因为预处理串在真实字符之间插入了#，回文半径每增加1，在半径内对应原串的真实字符数量增加1，但最外两侧都是#或者极值，减掉1正好是原串长度。如果你只需要返回长度，直接取p数组最大值即可；如果你需要返回具体回文子串，还需要记下最大半径对应的中心下标，再用(center - p[center]) / 2换算回原串的起始位置。

实际操作中我建议加个System.out.println(Arrays.toString(t))和打印p数组调试一下，回文半径数组能直观看到哪些位置是直接继承的，哪些是while扩散的。

4. BFPRT：确定性O(n)的TopK选择，核心是“中位数的中位数”

4.1 快排partition的退化风险

快速排序的平均复杂度是O(n log n)，原因在于它选基准后能把数组大致对半分。但在TopK问题里，我们只需要递归处理一边，理想情况下每次问题规模减半，总复杂度O(n + n/2 + n/4 + …) = O(n)。

但这里有个隐藏风险：如果基准选得不好，比如数组已经有序，每次选到的基准都是最小值，那么partition之后一边是空、一边是n-1个元素，递归深度变成O(n)，总复杂度退化成O(n^2)。

BFPRT就是为了解决这个问题：不依赖随机性，而是通过一种精心设计的取基准方法，保证每次选出的基准至少有约30%的元素在它左边、30%在它右边。这样无论输入多恶意，递归规模都必然缩减，最坏情况O(n)。

4.2 五步法主流程

BFPRT的完整流程分五步，跟它的发明者Blum、Floyd、Pratt、Rivest、Tarjan的论文保持一致：

第一步，把数组按5个元素一组分组，最后一组可能不足5个。

第二步，对每组内部的5个元素做插入排序，取出每组的中位数。这里用插入排序是因为每组固定最多5个，排序代价是常数。

第三步，递归调用BFPRT，在由所有组中位数组成的数组中找到中位数，这个值记为pivot。这一步是递归的，不同于后面的递归选择——它递归的目的是找基准，而不是直接找答案。

第四步，用pivot作为基准，对整个数组执行三向partition（小于、等于、大于三段）。

第五步，根据目标位置落在三段中的哪一段，决定递归入口：如果在等于段，直接返回；如果在小于段，在左边递归找；如果在大于段，在右边递归找。

这个流程跟快速排序一样都是分治，但关键差异就是第一步到第三步：它保证了第四步的基准不是随便选的，而是一个已经被证明“足够居中”的值。

4.3 为什么是5个一组而不是3个或7个

这个点面试官特别喜欢追问。先说结论：选择5是经过推导的，3个一组无法证明最坏O(n)，5个一组可以，7个一组虽然也可以但常数更大。

粗略证明一下5的情况：

• 假设数组有n个元素，分成n/5组。
• 每组中位数集合的中位数是pivot，那么在这些组中位数中，至少有一半（约n/10个）小于等于pivot。
• 每一组有5个元素，其中如果有中位数小于等于pivot，那这一组内至少还有2个元素（小于等于中位数的）也小于等于pivot，也就是说至少有3个元素小于等于pivot。
• 因此，全局至少3 * n/10个元素小于等于pivot。同理，也至少有3 * n/10个元素大于等于pivot。

这意味着partition之后，两个子问题规模都不超过7n/10。

递归规模是T(n) <= T(n/5) + T(7n/10) + O(n)，解这个递推式得到O(n)。注意1/5 + 7/10 = 9/10 < 1，这个线性递归式能收敛成O(n)，关键就在这里。

如果用3个一组，只能推出n/6和5n/6，两者相加是1，递推式变成T(n) <= T(n/3) + T(5n/6) + O(n)，系数和大于1，无法证明线性界。用7个一组当然可以，但分组内排序的常数会变大，实际收益不大，所以教科书里默认5。

4.4 Java实现与复杂度直观证明

贴一个完整的Java实现：

public class BfprtSelector { public static int bfprt(int[] arr, int k) { if (arr == null || k < 1 || k > arr.length) { throw new IllegalArgumentException("invalid k"); } return select(arr.clone(), 0, arr.length - 1, k - 1); } private static int select(int[] arr, int left, int right, int targetIdx) { if (left == right) return arr[left]; int pivot = medianOfMedians(arr, left, right); int[] range = partition(arr, left, right, pivot); if (targetIdx >= range[0] && targetIdx <= range[1]) { return arr[targetIdx]; } else if (targetIdx < range[0]) { return select(arr, left, range[0] - 1, targetIdx); } else { return select(arr, range[1] + 1, right, targetIdx); } } private static int medianOfMedians(int[] arr, int left, int right) { int n = right - left + 1; int groupCount = (n + 4) / 5; int[] medians = new int[groupCount]; for (int i = 0; i < groupCount; i++) { int l = left + i * 5; int r = Math.min(l + 4, right); insertionSort(arr, l, r); medians[i] = arr[l + (r - l) / 2]; } if (medians.length == 1) return medians[0]; return select(medians, 0, medians.length - 1, medians.length / 2); } private static int[] partition(int[] arr, int left, int right, int pivot) { int lt = left - 1; int gt = right + 1; int i = left; while (i < gt) { if (arr[i] < pivot) { swap(arr, ++lt, i++); } else if (arr[i] > pivot) { swap(arr, --gt, i); } else { i++; } } return new int[]{lt + 1, gt - 1}; } private static void insertionSort(int[] arr, int l, int r) { for (int i = l + 1; i <= r; i++) { int temp = arr[i]; int j = i - 1; while (j >= l && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args) { int[] arr = {3, 1, 9, 2, 7, 5, 8, 4, 6, 0}; for (int k = 1; k <= arr.length; k++) { System.out.println("k=" + k + ": " + bfprt(arr, k)); } } }

注意：这里我直接修改了arr，所以bfprt方法里用arr.clone()保护原数组。如果你不想排序原数组，这个克隆是必要的。

分区返回的是等值区间的[range[0], range[1]]，如果目标索引落在这个区间，就可以直接返回，因为所有该值都是第K小。

4.5 工程建议：什么时候别用BFPRT

说句实话，工程上我基本不用BFPRT。为什么？因为它的常数太大了：每轮递归都要做分组、组内插入排序、递归找中位数，然后再三向partition。对于一个几百万级别的整数数组，Java自带的Arrays.sort配合二分查找或者优先队列，实际耗时都比BFPRT快很多。

BFPRT真正的价值在于理论确定性：如果你面对的是恶意构造的数据，或者你的系统不能容忍任何一次退化到O(n^2)，那它才是不二选择。比如某些实时系统，数据来源不可信，有人可能故意构造有序数组让快速选择退化，这时候BFPRT就是安全的选择。

如果面试问TopK，我一般这样答：先说暴力排序O(n log n)，再说基于堆的O(n log k)方案，最后说快速选择平均O(n)，然后单独把BFPRT的确定性O(n)作为加分项讲清楚。这样既有层次感，也能展示理论深度。

5. 横向对比与应试实战建议

5.1 复杂度与适用场景速查表

时间复杂度上三者都是线性，但注意常数差异很大：KMP和Manacher是真正的低常数线性，BFPRT常数大但可控。

5.2 面试中的识别信号与选题策略

看到“找所有子串里满足某个模式条件的最长子串”，KMP和Manacher都有可能出现，区别在于条件是什么。如果条件跟重复子串、前缀后缀相关，优先KMP；如果条件明确是回文，毫不犹豫上Manacher。

看到“无序数组找第K小/大”，先不要急着写BFPRT。面试官通常期待你从堆方案聊起，毕竟堆方案在流式数据场景更实用。只有当面试官追问“最坏情况下还能O(n)吗”，或者题目明确要求确定性线性时间，才需要把BFPRT拿出来。

有一个识别KMP的常见信号：主串和模式串的匹配过程只能从左到右扫一遍，不能回头。有些题表面上是别的类型，实际上是KMP，比如求字符串最长重复子串、求一个串在另一个串中出现的次数，这些都是KMP的变体。

5.3 三个算法背后的“状态设计”思维

三个算法的难点都在于“状态数组里到底存什么”。

KMP的next数组存的是“匹配到当前字符失配时，模式串的指针应该回到哪里”，它本质是一个自动机的转移表。理解到这个程度，你就不会把next数组和“当前字符的最长前后缀”搞混了。

Manacher的p数组存的是“以当前位置为中心的最长回文半径”，但真正巧妙的是它利用镜像位置初始化，这里的核心思想是回文串的对称性是一种“全局约束”，可以跨位置共享信息。

BFPRT的中位数数组存的是“每5个元素的中位数”，它的作用是让基准选择可控。核心思想是：不要随便选基准，先花一点额外代价把基准“校准”到中间位置。

我经常在面试辅导里说一句话：算法题=暴力解+状态设计+信息复用。这三个算法是这句话最典型的三组注解。

5.4 刷题顺序与自测清单

我的建议是三个算法分开刷，同一个算法集中刷3到5道题，不要混着来：

KMP先刷入门级的“在文本串中找模式串”，再刷“统计模式串出现次数”“重复子串问题”这类变形。刷的时候一定要亲手计算一遍abacaba的next数组，并且用代码打印出来对照，这一步比多写五道题都管用。

Manacher先刷“求最长回文子串长度”，再刷“求具体回文子串”“统计回文子串个数”。每道题都打印一下preprocess之后的数组和p数组，看清楚哪些回文半径是靠镜像继承的，哪些是扩散出来的。

BFPRT先自己实现一遍，然后写个测试随机生成数组，跟排序后取值对比结果，最后试试用有序数组input，验证它确实不会退化到O(n^2)。

自测清单我就三句话：KMP的next数组能手推、Manacher的“right - i”知道为什么取min、BFPRT知道为什么6个元素以上才有分组意义（少于5个直接组内排序取中位数）。这三个问题能闭卷答上来，说明你真的理解了，不是背下来的。

最后分享一个我自己的调试习惯：这类算法最怕的就是数组越界和边界差一。我每次写完都会在关键循环里打印索引和数组内容，跑几个构造出来的极端用例，比如模式串只有一个字符、字符串全是同一个字符、数组长度恰好是5或6。这些边界用例一旦过了，基础逻辑基本就稳了。