[ Palindromic Tree ] 回文樹(回文自動機)

回文樹是去年新出的資料結構，由一個俄羅斯codeforces的紅人Mikhail Rubinchik在2014年發明的(http://codeforces.com/blog/entry/13959)，雖然名子直接翻譯叫回文樹，但他長的比較像一個自動機，所以也有很多人翻回文自動機。
在構造它之前，我們必須先證明一個長度n的字串其不同的回文子字串個數<=n，什麼是不同的回文子字串?就是長的不同的回文子字串，及把出現位置不同但形狀一樣的回文子字串當做是同樣的子字串。

證明:

1. 由左往右一個一個增加字符，則新產生的回文子字串其結尾一定是當前增加的字符x
2. 考慮以當前位置為結尾的最長回文x......x，顯而易見的，若產生除了x......x之外其它的回文子串，則必定被x......x所包含
3. 若增加字符x後，產生了除了x......x之外其它的回文子串，則根據回文的性質，其一定早已在x......的部分理出現(例:假設S是對稱點x...S.xax，因為回文的性質所以S的另一邊也會出現相同的字串xax.S.xax)
4. 因此每增加一個字符最多只會產生一個新的回文子字串，而長度為n的字符串最多只會產生n種不同的回文子字串

接下來進行回文自動機元素的詳細解說:

回文自動機包含以下元素:

1. 狀態St，所有節點的集合，一開始兩個節點，0表示偶數長度串的根和1表示奇數長度串的根
2. last 新增加一個字符後所形成的最長回文串的節點編號
3. s 當前的字符串(一開始設s[0]=-1(可以是任意一個在串S中不會出現的字符))
4. n 表示添加的字符個數

每個節點代表一個不同的回文子字串，我們在每個節點會儲存一些數值:

1. len 表示所代表的回文子字串長度
2. next[c] 表示所代表的回文子字串在頭尾各增加一個字符c後的回文字串其節點編號
3. fail 表示所代表的回文子字串不包括本身的最長後綴回文子串的節點編號
4. cnt(非必要) 表示所代表的回文子字串在整體字串出現的次數(在建構完成後呼叫count()才能計算)
5. num(非必要) 表示所代表的回文子字串其後綴為回文字串的個數

注意一開始必須先將狀態初始化St[0].len=0，St[1].len=-1，last=0，s[0]=-1，n=0

關於構造方法及圖片說明請參考:http://blog.csdn.net/u013368721/article/details/42100363
概念請參考:http://blog.csdn.net/MaticsL/article/details/43651169
證明請參考:http://yqcmmd.com/index.php/2015/03/30/746/

最後提供模板(使用STL vector)，因為St的元素在解題的過程中常會被用到所以就不封裝了:

[ Heavy-Light Decomposition ] 樹鏈剖分模板+LCA

在某些狀況下，我們希望對樹上a點到b點的路徑進行修改或查詢的動作，而且這些動作用一般的樹壓平RMQ或是離線處理無法完成的，這個時候我們可以利用特殊的方法將樹拆成長鏈。
長鏈可以搭配良好的資料結構。只要找出樹上所有長鏈，每條長鏈套用線段樹、BIT、Sparse Table、BST、Heap，就能降低時間複雜度。

可以利用簡單的做法將dfs序切成許多長鏈:

1. 首先先設定其中一點為根，算出每個子樹有多少節點
2. 樹上每個節點各自連向最大的子樹，相連的部分會自然形成鏈

通常步驟二會進行一次dfs，每次朝著最大的子樹走，每個節點記錄其時間戳記及所在的鏈(通常是記鏈首)，這樣就可以將樹壓平的結果切成許多鏈，使得樹鏈剖分同時可以做到樹壓平的操作。

我們可以進行一個簡單的證明:

• 假設節點數為V，由根往任意葉節點走，一旦遇到新鏈，新鏈的子樹必小於等於原鏈子樹，剩下的節點數量不到一半，所以沿途最多遇到 logV 條鏈。

因為一條路徑藉由 LCA 拆成兩段，沿途最多遇到 2*logV 條鏈，所以在任意兩點a,b間最多只需要進行2*logV次的區間操作，若是套線段樹之類的結構可以做到\(\ord{log^2V}\)
這些操作都可以在求LCA的過程中完成:

若樹鏈剖分的目的只是為了求LCA，build_link()及find_lca()有更好的做法:
這就只需進行一次DFS

[ Suffix Array Longest Common Prefix (LCP) ] 後綴數組之最長共同前綴(高度數組)

不解釋了，可以在\(\ord N \)時間內得到，N是字串長度
以下提供模板:

[ Suffix Array SA-IS Algorithm ] 後綴數組線性SA-IS算法

SA-IS是我目前看過最快的線性後綴數組演算法，但是做為競賽用途而進行簡化後他的效率在某些硬體上會比DC3慢，不過記憶體使用量是DC3的1/3~1/2倍，而最短的實現code也比DC3短很多，因此我認為這是十分優秀的算法

因為某些SA-IS的實作方式會利用傳入的陣列s的空間進行計算，因此傳入的陣列s必須是int範圍，而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過，因此必須給字串先做以下處理:

假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2
關於SA-IS算法的論文請看這裡:
Two Efficient Algorithms for Linear Time Suffix Array Construction

關於SA-IS算法的教學(專利申請文)請看這裡:
后缀数组构造方法  CN 102081673 A

SA-IS的教學投影片:
https://www.cs.helsinki.fi/u/tpkarkka/opetus/11s/spa/lecture11.pdf

SA-IS中文教學:
https://riteme.github.io/blog/2016-6-19/sais.html

如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

以下將會提供一些SA-IS的實做模板

1.台大黑暗code界的黑暗codebook:
其實這段code本來是被壓縮得更短，而且用到非常多的記憶體，不過經過卦長的改良後成功減少記憶體的使用並將他排版成正常人能看得懂的樣子
而這裡的MXN則是字串的最長長度(假設字元數<字串長度)

2.卦長自行實作的模板(記憶體用量少):
為了簡化實作方法及減少記憶體的使用，因此將計算後剩下的空間進行重複利用，壓縮後只需要這些記憶空間，而傳入的陣列s可以直接傳入char陣列，因此對使用者來說是非常方便的一份code
這裡的MXN則是字串的最長長度(假設字元數<字串長度)

3.論文提供的實作code:
這是其中一個比DC3快的code，而且記憶體使用量是最少的，但是長度很長就是了，不適合在比賽時使用

4.超快記憶體使用超少的模板庫code:
https://gist.github.com/jacky860226/1d33adad858eef71bfe18120d8d69e6d#file-sa-is-very-fast-cpp
因為長度太長所以就直接貼上網址了，沒有人會在比賽時寫這種東西

[ Difference Cover modulo 3, DC3 ] 後綴數組線性DC3演算法

DC3 是歷史上第一個線性時間的後綴數組演算法，而且相對於 SA-IS 來說更容易作為教材。

這是 DC3 的原始論文：
https://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf

首先是後綴分類。我們會將所有後綴根據其起始位置 $i$ 對 3 的餘數進行分類，形成三種不同的類型：

• Type A ($i$%3=0):
  這類後綴的起始位置是 3 的倍數。它們不會直接參與初始排序，而是透過 Type B 的排序結果間接排序。
• Type B1 ($i$%3=1):
  這類後綴會與 Type B2 一起組成 Type B 後綴集合，並進行初步排序。
• Type B2 ($i$%3=2):
  同樣屬於 Type B 後綴集合，與 B1 一起進行排序。

以 "mississkp" 為例，為了方便操作我們在其尾端加入兩個哨兵字元 '\0'。

如圖1 所示，首先我們對於每個 Type B 後綴，我們取出其前三個字元作為排序鍵值，將這些三元組視為新的字元（透過 radix sort 將三元組映射為整數，實作上呼叫了三次 counting sort），並對它們進行排序。若排序後的鍵值唯一，則排序完成；否則需將這些鍵值壓縮成新的字母表，並遞迴呼叫 DC3 來排序這個縮小版的問題。

圖1

如圖2 所示，此時 Type B 後綴的排名已經確定了。對於每個 Type A 後綴 i，我們無法直接比較整個後綴（因為效率問題），但可以利用 Type B 的排名來構造一個排序鍵值：

• 對於每個 Type A 後綴 i，我們取：

• $S[i]$：當前字元
• $R[i+1]$：Type B1 後綴的排名（因為 i+1 % 3 = 1）

一次 counting sort 後，我們得到了  Type A 後綴的排名。

圖2

接著我們要合併兩種後綴的排序結果，可以使用 std::merge 合併，但須要寫一個 $\ord{1}$ 的比較函數。設比較函數 $cmp(x,y)$， $x$ 是某個 Type B 後綴的編號，$y$ 是某個 Type A 後綴的編號：

1. $S[x]\ne S[y]$：
   直接比較 $S[x],\;S[y]$
2. Type B1 後綴 ($x$ % 3 = 1)：
   此時 $x+1$ 和 $y+1$ 都是 Type B 後綴，直接比較 $R[x+1],\;R[y+1]$
3. Type B2 後綴 ($x$ % 3 = 2)：
   此時 $x+1$ 是 Type A 後綴， $y+1$ 是 Type B 後綴，直接呼叫 $!cmp(y+1,x+1)$

圖3 展示了當前範例的合併結果，DC3 算法到這邊就結束了。

整體時間複雜度 $T(n)=T(2n/3)+\ord{n}=\ord{n}$，但要注意空間使用量
$$M(n) =
\begin{cases}
n + \delta(n) + 2, & n \leq 2 \\
n + \delta(n) + 2 + M\left(\left\lfloor \frac{2(n + \delta(n))}{3} \right\rfloor\right), & n > 2\end{cases}\\ \delta(n) = [n\equiv 1\left(\bmod 3\right)]$$

根據 AI 的推導 $M\left(n\right)\le 3n+\left\lfloor 4\log_{1.5}\left(n-2\right)\right\rfloor+1$。

圖3

2025/10/10 更新：有人發現我原始的程式碼在當 n%3=1 遞迴時在 Type B1 和 Type B2 之間沒有隔離符號，有可能導致這兩類後綴排序錯誤，聽說我一開始的參考資料 ([2009] 后缀数组——处理字符串的有力工具 by. 罗穗骞) 也有一樣的問題，因此我花了點時間重寫了 DC3 的教學。

錯誤原因如圖4 所示，若不加上這個哨兵字元的話，後綴 7 就不會被加入遞迴運算，這樣會導致某個 Type B1 後綴將不是自己正確後綴的 Type B2 後綴連接起來排序導致結果錯誤。

圖4

以下提供模板(註解是請 AI 寫的，拿掉之後程式碼應該會很短):

[ Suffix Array Prefix doubling algorithms ] 後綴數組倍增算法

後綴數組(又稱尾碼陣列)是一個十分強大的字串處理武器，大部分的問題都可以用它來解決，它可以幾乎做到所有後綴樹(Suffix Tree)能做到的事，所以這邊就不介紹後綴樹了

因為後綴數組可以由後綴樹進行遍歷轉換而來，而構造後綴樹僅需花費線性的時間，所以構造後綴數組的時間可為線性\(\ord N\)，但是後綴數組本身就是為了減少構造後綴樹的空間與代碼量而被發明出來的，直接由後綴樹轉換是沒意義的
但是仍然有其他線性構造後綴數組的方法，像是DC3、SA-IS等會在下一篇介紹，這次要講的是比較簡單常用的方法-----倍增法
關於後綴數組的使用說明可以參考《后缀数组——处理字符串的有力工具》
關於倍增法的說明可以參考 演算法筆記-SuffixArray 的部分
這邊提供\(\ord{N*logN*logN}\)及\(\ord{NlogN}\)的模板

\(\ord{N*logN*logN}\):
\(\ord{NlogN}\):
注意此方法必須要在字元集大小為常數的情況下有效，否則必須離散化

所需的陣列長度只需要與字串陣列相同即可
當然\(N*logN*logN\)的做法會比較值觀，\(NlogN\)的方法則是利用radix_sort進行的，radix_sort本來在倍增的時候要先排序第一關鍵字跟第二關鍵字，但是第二關鍵字排序的結果可以用已經求好的SA直接求出來
對radix_sort還不了解的人請看這個網頁:https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

英文字母大小寫轉換特殊做法

假設有一個題目是這樣的:
        給定一串英文字母，請將大寫的部分轉成小寫，小寫的部分轉成大寫並輸出

一般我們會用if或是三元運算子做判斷，但是這太麻煩了
經過觀察發現，摁合一個小寫字母ascii與其對應的大寫字母ascii相差皆為32，
而其二進位編碼剛好允許透過 xor 32的方式進行轉換，但是32這個數字不好記，又可以發現ascii 32='空白'，而以下的code就可以將大小寫互換:

1 2 3 4 5 6 7 8

#include<stdio.h> char s[1000005]; int main(){ scanf("%s",s); for(int i=0;s[i];++i)putchar(s[i]^' ');puts(""); for(int i=0;s[i];++i)putchar(s[i]^32);puts(""); return 0; }

兩種寫法會有相同的效果