字典樹：https://blog.csdn.net/hebtu666/article/details/83141560
后綴樹：后綴樹，就是把一串字符的所有后綴保存并且壓縮的字典樹。
?
相對于字典樹來說，后綴樹并不是針對大量字符串的，而是針對一個或幾個字符串來解決問題。比如字符串的回文子串，兩個字符串的最長公共子串等等。
比如單詞banana，它的所有后綴顯示到下面的。0代表從第一個字符為起點，終點不用說都是字符串的末尾。
以上面的后綴，我們建立一顆后綴樹。如下圖，為了方便看到后綴，我沒有合并相同的前綴。
把非公共部分壓縮：
后綴樹的應用：
（1）查找某個字符串s1是否在另外一個字符串s2中：如果s1在字符串s2中，那么s1必定是s2中某個后綴串的前綴。
（2）指定字符串s1在字符串s2中重復的次數：比如說banana是s1，an是s2，那么計算an出現的次數實際上就是看an是幾個后綴串的前綴。
（3）兩個字符串S1，S2的最長公共部分（廣義后綴樹）
（4）最長回文串（廣義后綴樹）
?
關于后綴樹的實現和應用以后再寫，這次主要寫后綴數組。
在字符串處理當中，后綴樹和后綴數組都是非常有力的工具。其實后綴數組是后綴樹的一個非常精巧的替代品，它比后綴樹容易編程實現，能夠實現后綴樹的很多功能而時間復雜度也不太遜色，并且，它比后綴樹所占用的空間小很多。可以說，在信息學競賽中后綴數組比后綴樹要更為實用。
?
后綴數組：就是把某個字符串的所有后綴按照字典序排序后的數組。（數組中保存起始位置就好了，結束位置一定是最后）
先說如何計算后綴數組：
倍增的思想，我們先把每個長度為2的子串排序，再利用結果把每個長度為4的字串排序，再利用結果排序長度為8的子串。。。直到長度大于等于串長。
設置sa[]數組來記錄排名：sa[i]代表排第i名的是第幾個串。
結果用rank[]數組返回，rank[i]記錄的是起始位置為第i個字符的后綴排名第幾小。
我們開始執行過程：
比如字符串abracadabra
長度為2的排名：a ab ab ac ad br br ca da ra ra,他們分別排第0，1，2，2，3，4，5，5，6，7，8，8名
sa數組就是11(空串),10(a),0(ab),7,3,5,1,8,4,6,2,9(ra排名最后)
這樣，所有長度為2的子串的排名就出來了，我們如何利用排名把長度為4的排名搞出來呢？
abracadabra中，ab,br,ra這些串排名知道了。我們把他們兩兩合并為長度為4的串，進行排名。
比如abra和brac怎么比較呢？
用原來排名的數對來表示
abra=ab+ra=1+8
brac=br+ac=4+2
對于字符串的字典序，這個例子比1和4就比出來了。
如果第一個數一樣，也就是前兩個字符一樣，那再比后面就可以了。
簡單說就是先比前一半字符的排名，再比后一半的排名。
具體實現，我們可以用系統sort，傳一個比較器就好了。
?
還有需要注意，長度不可能那么湊巧是2^n，所以 一般的，k=n時，rank[i]表示從位置i開始向后n個字符的排名第幾小，而剩下不足看個字符，rank[i]代表從第i個字符到最后的串的排名第幾小，也就是后綴。
保證了每一個后綴都能正確表示并排序。比如k=4時，就表示出了長度為1，2，3的后綴：a,ra,bra.這就保證了k=8時，長度為5，6，7的后綴也能被表示出來：4+1，4+2，4+3
還有，sa[0]永遠是空串，空串的排名rank[sa[0]]永遠是最大。
int n;
int k;
int rank[MAX_N+1];//結果（排名）數組
int tmp[MAX_N+1];//臨時數組
//定義比較器
bool compare(int i,int j)
{if(rank[i]!=rank[j])return rank[i]<rank[j];//長度為k的子串的比較int ri=i+k<=n ? rank[i+k] : -1;int rj=j+k<=n ? rank[j+k] : -1;return ri<rj;
}void solve(string s,int *sa)
{n=s.length;//長度為1時，按字符碼即可，長度為2時就可以直接用for(int i=0;i<=n;i++){sa[i]=i;rank[i]=i<n ? s[i] : -1;//注意空串為最大}//由k對2k排序，直到超范圍for(k=1;k<=n;k*=2){sort(sa,sa+n+1,compare);tmp[sa[0]=0;//空串for(int i=1;i<=n;i++){tmp[sa[i]]=tmp[sa[i-1]]+(compare(sa[i-1],sa[i]) ? 1 : 0);//注意有相同的}for(int i=0;i<=n;i++){rank[i]=tmp[i];}}
}具體應用以后再寫。。。。。
?
?
