面试的三个关键算法

一、KMP算法

1.定义

str1中是否包含str2，返回初始下标。

2.思路

（1）暴力匹配
基于str1，依次匹配str2，时间复杂度为O(MN)。
（2）KMP算法
基于str2建立一组信息，最大前缀和后缀的匹配。next数组，时间复杂度为O(N)。

3.KPM扩展

（1）给定两个二叉树T1和T2，返回T1的某个子树结构是否与T2的结构相等。
将两个二叉树转换为字符串，再用KMP算法判断str1是否包含str2。

二、Manacher算法

1.定义

在一个字符串中找到最长的回文子串。
子串（子数组）必须是连续的，子序列顺序不变但可以不连续。

2.思路

（1）笨办法
添加特殊字符，例如#（不一定要和原字符串不一样），从一个数开始向两边扩，判断左右两个数是否相等。奇回文和偶回文都可以解决。
（2）马拉车算法

3.扩展

题目：给定一个字符串str1，只能往str1的后面添加字符变成str2，要求str2整体都是回文串且最短。
解题思路：找到包含最后一个字符的回文子串，然后添加不在子串内的字符的逆序。

三、BFPRT算法

1.定义

在一个无序数组中求第k（k≥1）小（大）的数，时间复杂度要求为O(N)。

2.思路

（1）随机快排的partition
看等于的数是否命中第k小（即判断小于划分值的区间数据的个数是否为k-1，而这k-1个数是不需要进行排序的），没有命中就接着partition，平均时间复杂度为O(N)。
（2）BFPRT算法

• 关键在于划分值的选择。

1. 将数组划分为每五个数一个组，不足五个的单独一组，O(1)。
2. 组内进行排序，组与组之间不排序，O(1)×N/5，即O(N)。
3. 将每个组的上中位数取出作为新的数组，长度为N/5，数组不一定是有序的。递归调用自身，求新数组的中位数，即第N/10小的数，T(N/5)。
4. 将其作为划分值，对原数组进行partition，O(N)。
5. 左边或者右边数组进行递归，最大为T(7N/10)。
   整体时间复杂度为T(N)=T(N/5)+T(7N/10)+O(N)，可以证明收敛到O(N)。

• 为什么要选这个数为划分值？
  因为它至少可以确定的排除3N/10的数。
• 为什么要选择5进行分组？
  因为这个算法是由五个人研究出来的！2333333
  只要能证明收敛到O(N)，选择其他的数也是可以的。