[ Persistent Binary Index Tree ] 持久化BIT

(二分索引樹)BIT是一種容易實現的資料結構，但在持久化的應用上是非常困難的，但我們可以犧牲些許的複雜度來簡化其實現方式

一般區間和的BIT長這樣:

這是持久化的版本(也可以用pair來實作):
可以知道其更新的複雜度為\(\ord{logN}\)，查詢複雜度為\(\ord{logN*logQ}\)，Q是查詢次數

[ Suffix Automaton ] 後綴自動機

定義字串S的後綴自動機是一種自動機可以接受S的所有後綴，其狀態最多為2*strlen(s)-1個，雖然理論複雜，但其構造方式十分簡單，且它可以用來處理一些後綴數組或事後綴樹的問題，因此是一個十分強大的資料結構。
後綴自動機大致的構造方式是將字串擔一字元按順序進行插入，插入的均攤時間為\(\ord 1\)，關於詳細的情形可以在 http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html 這個網站中得到
而關於複雜度及詳細的證明請參考陈立杰的簡報
關於狀態數為線性的證明在19~21頁，有詳細的圖文解說
這個網站包含其一些延伸資料結構http://maskray.me/blog/2013-05-10-suffix-automaton
為了減少記憶體的使用，以vector代替指標維護狀態
以下提供模板:

[ Aho-Corasick Automaton ] AC自動機

Aho-Corasick Automaton，該算法在1975年產生於貝爾實驗室，是著名的多模匹配算法之一
在了解AC自動機之前，必須先學會字典樹Trie的使用，簡單的來說，他是將KMP的fail函數應用在Trie做為失敗邊。
有\(n\)個字串\(B_0,B_1,...,B_{n-1}\) 要匹配字串\(A\)，則一般用KMP的算法會得到\(\ord{\sum_{i=0}^{n-1}(|A|+|B_i|)}\)，使用AC自動機的演算法其複雜度為\(\ord{|A|+\sum_{i=0}^{n-1}|B_i|}\)，必須用DP

關於AC自動機的介紹請看這裡

以下為AC自動機的模板

[ Knuth-Morris-Pratt Algorithm ] 克努斯-莫里斯-普拉特(KMP)算法

這是一個大家很常聽到的字串匹配演算法，較Z Algorithm複雜，但更為通用，C++的string就有內建(string::find)。假設要以B匹配A，則會先建立B的部分匹配表(又叫做失配函數)，其定義如下:
     fail(i)=max(滿足B[0,k]=B[i-k,i]的所有k)
同樣的也可以在線性時間來完成
對於KMP演算法的詳細情況請參考這裡
以下提供fail function陣列及匹配的實作

[ Manacher's algorithm ] Linear time Longest palindromic substring 線性最長回文子串

Manacher演算法是Z algorithm的變種，可以說是雙向的Z algorithm，複雜度也是\(\ord N\)
其Z function定義如下:
     Z(i)=以位置i為中心的最長回文半徑
但是這樣只能處理回文長度是奇數的子串，因此必須幫字串做一些修改

假設原來的字串是: "asdsasdsa"
修改後變成: "@#a#s#d#s#a#s#d#s#a#"
其中'@'及'#'為不同字元且皆未在原字串中出現過
其Z function陣列為: 0 1 2 1 2 1 6 1 2 1 10 1 2 1 6 1 2 1 2 1
則 最大的數字-1 (10-1=9)就是我們要的答案

這裡提供Manacher algorithm產生Z function陣列的實作:

[ Z algorithm ] Linear-time pattern matching 線性字串匹配 Z演算法

定義一個字串S的Z function:
    Z(i)=0 如果i=0 or S[i]!=S[0]     否則
    Z(i)=max(所有的k滿足 S[0,k-1]=S[i,i+k-1])
從Z function的定義，假設要在字串A裡面匹配字串B
可以先建構字串S=B+(A和B都沒有的字元)+A的Z function陣列
若Z[i]=lenB則表示在A[i-lenB]有一個完全匹配
這裡提供兩個可以\(\ord{N}\)時間求出Z function陣列的方法:

對一個特殊構建的數據strlen(s)=10000000其效率平均為
z_alg1:   0.106s
z_alg2:   0.089s
這兩種方法的想法是相同的
我們可以知道第一個方法是較為直觀好寫的，但是運算量較大且調用min函數的效率並不高
但仍在可接受的範圍

[ skew heap ] implementation 斜堆 實作

斜堆(Skew heap)也叫自適應堆(self-adjusting heap)，它是(重量)左偏樹的一個變種。
相較於(重量)左偏樹，斜堆不需記錄其高度或是節點個數(size)等附加域，其合併(merge)的方式也較為簡潔，效率也較高。和(重量)左偏樹一樣，斜堆的push、pop的時間複雜度為\(\ord{log \; n}\)、查詢最值為\(\ord 1\)。
關於複雜度分析
以下提供斜堆的實作，使用方法與STL priority_queue相似