一、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.定義
在一個字符串中找到最長的回文子串。
子串（子數組）必須是連續(xù)的，子序列順序不變但可以不連續(xù)。
2.思路
（1）笨辦法
添加特殊字符，例如#（不一定要和原字符串不一樣），從一個數開始向兩邊擴，判斷左右兩個數是否相等。奇回文和偶回文都可以解決。
（2）馬拉車算法
3.擴展
題目：給定一個字符串str1，只能往str1的后面添加字符變成str2，要求str2整體都是回文串且最短。
解題思路：找到包含最后一個字符的回文子串，然后添加不在子串內的字符的逆序。
三、BFPRT算法
1.定義
在一個無序數組中求第k（k≥1）?。ù螅┑臄?，時間復雜度要求為O(N)。
2.思路
（1）隨機快排的partition
看等于的數是否命中第k?。磁袛嘈∮趧澐种档膮^(qū)間數據的個數是否為k-1，而這k-1個數是不需要進行排序的），沒有命中就接著partition，平均時間復雜度為O(N)。
（2）BFPRT算法
- 關鍵在于劃分值的選擇。
- 將數組劃分為每五個數一個組，不足五個的單獨一組，O(1)。
- 組內進行排序，組與組之間不排序，O(1)×N/5，即O(N)。
- 將每個組的上中位數取出作為新的數組，長度為N/5，數組不一定是有序的。遞歸調用自身，求新數組的中位數，即第N/10小的數，T(N/5)。
- 將其作為劃分值，對原數組進行partition，O(N)。
- 左邊或者右邊數組進行遞歸，最大為T(7N/10)。
整體時間復雜度為T(N)=T(N/5)+T(7N/10)+O(N)，可以證明收斂到O(N)。
-
為什么要選這個數為劃分值？
因為它至少可以確定的排除3N/10的數。 -
為什么要選擇5進行分組？
因為這個算法是由五個人研究出來的！2333333
只要能證明收斂到O(N)，選擇其他的數也是可以的。
