[ Persistent Binary Index Tree ] 持久化BIT

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

一般區間和的BIT長這樣:

	int n;
	int tree[100005];
	#define lowbit(x) x&(-x)
	inline void modify(int x,int d){
	for(;x<=n;x+=lowbit(x))tree[x]+=d;
	}
	inline int query(int x){
	int ans=0;
	for(;x;x-=lowbit(x))ans+=tree[x];
	return ans;
	}

view raw BIT.cpp hosted with ❤ by GitHub

這是持久化的版本(也可以用pair來實作):

	#include<vector>
	#include<algorithm>
	#define lowbit(x) x&(-x)
	struct P{
	int data,id;
	P(int d=0,int i=0):data(d),id(i){}
	inline friend bool operator<(const P &a,const P &b){
	return a.id<b.id;
	}
	};
	int n,now;
	std::vector<P >tree[100005];
	inline void init(){
	now=0;
	for(int i=1;i<=n;++i)tree[i].clear(),tree[i].push_back(P());
	}
	inline void modify(int x,int d){
	for(;x<=n;x+=lowbit(x))tree[x].push_back(P(tree[x].back().data+d,now));
	++now;
	}
	inline int query(int x,int id){/*查詢第id次操作的區間和，id從0開始計算*/
	int ans=0;
	std::vector<P >::iterator a;
	for(;x;x-=lowbit(x)){
	a=std::upper_bound(tree[x].begin(),tree[x].end(),P(0,id))-1;
	ans+=a->data;
	}
	return ans;
	}

view raw Persistent BIT.cpp hosted with ❤ by GitHub

可以知道其更新的複雜度為$\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代替指標維護狀態
以下提供模板:

	#ifndef SUFFIX_AUTOMATON
	#define SUFFIX_AUTOMATON
	#include<vector>
	template<char L='a',char R='z'>
	struct suffix_automaton{
	struct node{
	int ch[R-L+1],fa,len;
	node(int l=0):fa(0),len(l){
	for(int i=0;i<=R-L;++i)ch[i]=0;
	}
	};
	std::vector<node >S;
	int tail,u,v,np,vp;
	suffix_automaton():S(2),tail(1){S[0].fa=0;}
	inline void add(int c){
	c-=L;
	u=tail;
	S.push_back(node(S[u].len+1));
	tail=np=S.size()-1;
	for(;u&&!S[u].ch[c];u=S[u].fa)S[u].ch[c]=np;
	if(!u)S[np].fa=1;
	else{
	v=S[u].ch[c];
	if(S[v].len==S[u].len+1)S[np].fa=v;
	else{
	S.push_back(S[v]);
	vp=S.size()-1;
	S[vp].len=S[u].len+1;
	S[v].fa=S[np].fa=vp;
	for(;u&&S[u].ch[c]==v;u=S[u].fa)S[u].ch[c]=vp;
	}
	}
	}
	inline int size(){return S.size()-2;}
	};
	#endif

view raw Suffix Automaton.cpp hosted with ❤ by GitHub

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

	#ifndef SUNMOON_AHO_CORASICK_AUTOMATON
	#define SUNMOON_AHO_CORASICK_AUTOMATON
	#include<queue>
	#include<vector>
	template<char L='a',char R='z'>
	class ac_automaton{
	private:
	struct joe{
	int next[R-L+1],fail,efl,ed,cnt_dp,vis;
	joe():ed(0),cnt_dp(0),vis(0){
	for(int i=0;i<=R-L;++i)next[i]=0;
	}
	};
	public:
	std::vector<joe> S;
	std::vector<int> q;
	int qs,qe,vt;
	ac_automaton():S(1),qs(0),qe(0),vt(0){}
	inline void clear(){
	q.clear();
	S.resize(1);
	for(int i=0;i<=R-L;++i)S[0].next[i]=0;
	S[0].cnt_dp=S[0].vis=qs=qe=vt=0;
	}
	inline void insert(const char *s){
	int o=0;
	for(int i=0,id;s[i];++i){
	id=s[i]-L;
	if(!S[o].next[id]){
	S.push_back(joe());
	S[o].next[id]=S.size()-1;
	}
	o=S[o].next[id];
	}
	++S[o].ed;
	}
	inline void build_fail(){
	S[0].fail=S[0].efl=-1;
	q.clear();
	q.push_back(0);
	++qe;
	while(qs!=qe){
	int pa=q[qs++],id,t;
	for(int i=0;i<=R-L;++i){
	t=S[pa].next[i];
	if(!t)continue;
	id=S[pa].fail;
	while(~id&&!S[id].next[i])id=S[id].fail;
	S[t].fail=~id?S[id].next[i]:0;
	S[t].efl=S[S[t].fail].ed?S[t].fail:S[S[t].fail].efl;
	q.push_back(t);
	++qe;
	}
	}
	}
	/*DP出每個前綴在字串s出現的次數並傳回所有字串被s匹配成功的次數O(N+M)*/
	inline int match_0(const char *s){
	int ans=0,id,p=0,i;
	for(i=0;s[i];++i){
	id=s[i]-L;
	while(!S[p].next[id]&&p)p=S[p].fail;
	if(!S[p].next[id])continue;
	p=S[p].next[id];
	++S[p].cnt_dp;/*匹配成功則它所有後綴都可以被匹配(DP計算)*/
	}
	for(i=qe-1;i>=0;--i){
	ans+=S[q[i]].cnt_dp*S[q[i]].ed;
	if(~S[q[i]].fail)S[S[q[i]].fail].cnt_dp+=S[q[i]].cnt_dp;
	}
	return ans;
	}
	/*多串匹配走efl邊並傳回所有字串被s匹配成功的次數O(N*M^1.5)*/
	inline int match_1(const char *s)const{
	int ans=0,id,p=0,t;
	for(int i=0;s[i];++i){
	id=s[i]-L;
	while(!S[p].next[id]&&p)p=S[p].fail;
	if(!S[p].next[id])continue;
	p=S[p].next[id];
	if(S[p].ed)ans+=S[p].ed;
	for(t=S[p].efl;~t;t=S[t].efl){
	ans+=S[t].ed;/*因為都走efl邊所以保證匹配成功*/
	}
	}
	return ans;
	}
	/*枚舉(s的子字串∩A)的所有相異字串各恰一次並傳回次數O(N*M^(1/3))*/
	inline int match_2(const char *s){
	int ans=0,id,p=0,t;
	++vt;
	/*把戳記vt+=1，只要vt沒溢位，所有S[p].vis==vt就會變成false
	這種利用vt的方法可以O(1)歸零vis陣列*/
	for(int i=0;s[i];++i){
	id=s[i]-L;
	while(!S[p].next[id]&&p)p=S[p].fail;
	if(!S[p].next[id])continue;
	p=S[p].next[id];
	if(S[p].ed&&S[p].vis!=vt){
	S[p].vis=vt;
	ans+=S[p].ed;
	}
	for(t=S[p].efl;~t&&S[t].vis!=vt;t=S[t].efl){
	S[t].vis=vt;
	ans+=S[t].ed;/*因為都走efl邊所以保證匹配成功*/
	}
	}
	return ans;
	}
	/*把AC自動機變成真的自動機*/
	inline void evolution(){
	for(qs=1;qs!=qe;){
	int p=q[qs++];
	for(int i=0;i<=R-L;++i)
	if(S[p].next[i]==0)S[p].next[i]=S[S[p].fail].next[i];
	}
	}
	};
	#endif

view raw Aho-Corasick automaton.cpp hosted with ❤ by GitHub

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

	/*產生fail function*/
	inline void kmp_fail(char *s,int len,int *fail){
	int id=-1;
	fail[0]=-1;
	for(int i=1;i<len;++i){
	while(~id&&s[id+1]!=s[i])id=fail[id];
	if(s[id+1]==s[i])++id;
	fail[i]=id;
	}
	}
	/*以字串B匹配字串A，傳回匹配成功的數量*/
	inline int kmp_match(char *A,int lenA,char *B,int lenB,int *fail){
	int id=-1,ans=0;
	for(int i=0;i<lenA;++i){
	while(~id&&B[id+1]!=A[i])id=fail[id];
	if(B[id+1]==A[i])++id;
	if(id==lenB-1){/*匹配成功*/
	++ans;
	id=fail[id];
	}
	}
	return ans;
	}

view raw KMP.cpp hosted with ❤ by GitHub

[ 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陣列的實作:

	/*
	原字串: asdsasdsa
	先把字串變成這樣: @#a#s#d#s#a#s#d#s#a#
	*/
	inline void manacher(char *s,int len,int *z){
	int l=0,r=0;
	for(int i=1;i<len;++i){
	z[i]=r>i?min(z[2*l-i],r-i):1;
	while(s[i+z[i]]==s[i-z[i]])++z[i];
	if(z[i]+i>r)r=z[i]+i,l=i;
	}
	}

view raw Manacher.cpp hosted with ❤ by GitHub

[ 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陣列的方法:

	inline void z_alg1(char *s,int len,int *z){
	int l=0,r=0;
	z[0]=len;
	for(int i=1;i<len;++i){
	z[i]=r>i?min(r-i+1,z[z[l]-(r-i+1)]):0;
	while(i+z[i]<len&&s[z[i]]==s[i+z[i]])++z[i];
	if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
	}
	inline void z_alg2(char *s,int len,int *z){
	int l=0,r=0;
	z[0]=len;
	for(int i=1;i<len;++i){
	z[i]=i>r?0:(i-l+z[i-l]<z[l]?z[i-l]:r-i+1);
	while(i+z[i]<len&&s[i+z[i]]==s[z[i]])++z[i];
	if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
	}

view raw Z.cpp hosted with ❤ by GitHub

對一個特殊構建的數據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相似

	#include<functional>
	#ifndef SKEW_HEAP
	#define SKEW_HEAP
	template<typename T,typename _Compare=std::less<T> >
	class skew_heap{
	private:
	struct node{
	T data;
	node *l,*r;
	node(const T&d):data(d),l(0),r(0){}
	}*root;
	int _size;
	_Compare cmp;
	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	if(cmp(a->data,b->data))return merge(b,a);
	node *t=a->r;
	a->r=a->l;
	a->l=merge(b,t);
	return a;
	}
	void _clear(node *&o){
	if(o)_clear(o->l),_clear(o->r),delete o;
	}
	public:
	skew_heap():root(0),_size(0){}
	~skew_heap(){_clear(root);}
	inline void clear(){
	_clear(root);root=0;_size=0;
	}
	inline void join(skew_heap &o){
	root=merge(root,o.root);
	o.root=0;
	_size+=o._size;
	o._size=0;
	}
	inline void swap(skew_heap &o){
	node *t=root;
	root=o.root;
	o.root=t;
	int st=_size;
	_size=o._size;
	o._size=st;
	}
	inline void push(const T&data){
	_size++;
	root=merge(root,new node(data));
	}
	inline void pop(){
	if(_size)_size--;
	node *tmd=merge(root->l,root->r);
	delete root;
	root=tmd;
	}
	inline const T& top(){return root->data;}
	inline int size(){return _size;}
	inline bool empty(){return !_size;}
	};
	#endif

view raw skew heap.cpp hosted with ❤ by GitHub