\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年5月28日 星期四

[ Persistent Binary Index Tree ] 持久化BIT

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

一般區間和的BIT長這樣:

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

2015年5月14日 星期四

[ 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代替指標維護狀態
以下提供模板:

2015年5月9日 星期六

[ 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自動機的模板

2015年5月8日 星期五

[ 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陣列及匹配的實作

2015年5月7日 星期四

[ 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函數的效率並不高
但仍在可接受的範圍

2015年5月3日 星期日

[ skew heap ] implementation 斜堆 實作

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