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. KMPnext数组的本质是“用模式串匹配模式串”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]0next[2]看pattern[0..1]即ab前缀a和后缀b不相等所以next[2]0next[3]看pattern[0..2]即aba最长相等真前后缀是a长度1所以next[3]1next[4]看pattern[0..3]即abac前缀a/ab/aba后缀c/ac/bac没有相等的所以next[4]0next[5]看pattern[0..4]即abaca相等的前后缀是a长度1所以next[5]1next[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扩散时免去越界判断。处理后的字符串长度变为2n3原来的奇数回文和偶数回文在预处理串里都变成了奇数回文中心都是某个#或真实字符。统一成奇数以后处理逻辑就只剩一种。这里有一个换算关系很重要预处理串里的回文半径减去1正好等于原串的回文长度。比如原串aba以b为中心的回文半径在预处理串里是4从b到左边#、右边#都算上4减1等于3正好是aba的长度。这个关系网上很多文章不写清楚导致你就算跑通了代码也不知道为什么返回的是max(p) - 1还是max(p)。3.2 回文半径数组p[i]与最右边界rightManacher维护两个关键变量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 复杂度与适用场景速查表算法时间复杂度空间复杂度核心场景关键状态KMPO(nm)O(m)字符串匹配、子串查找next数组前缀函数ManacherO(n)O(n)最长回文子串回文半径数组p[i]、最右边界rightBFPRTO(n)O(n)无序数组寻找第K小/大中位数的中位数 pivot时间复杂度上三者都是线性但注意常数差异很大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。这些边界用例一旦过了基础逻辑基本就稳了。