字尾數組簡介
字尾數組（\(Suffix \ Array\)，簡稱 \(SA\)）是一種可以很好地處理字元串問題的優秀算法，它可以解決很多類型的字元串問題。
字尾數組主要解決的問題是給出一個字元串 \(S\)，将字元串 \(S\) 的每一個字尾都按照字典序升序排序，排序後依次輸出每一個字尾的第一個字元在原串中的位置。
暴力，\(\mathcal{O}(n^2 \log n)\)。
下面介紹兩種字尾數組的寫法：倍增法 \(\mathcal{O}(nlogn)\) 和 <code>DC3</code> 法 \(\mathcal{O}(n)\)。
倍增法
采用基數排序的思想。
按照字典序排列，若一一比較，肯定先從第一位開始比。
是以我們可以按照每個字尾的第一個字元排個序，這個操作相當于把這個字元串的每個字元排個序。
按照排序，接下來要比較排名一樣的字元的第二位。
然後複雜度就飛了。
但是，第二位我們其實已經比較過了。
因為要排序的是字尾，是以第 \(i\) 個字尾的第二個字元就是第 \(i+1\) 個字元，也就是已經排序好了，而第一位是第一關鍵字，第二位是第二關鍵字。
那麼就可以得到第二位的排序。
以此類推，可以利用倍增的思想，再利用已知去得出第四位的排序，再得出第八位的排序，以此類推。
不難得出，當所有字尾的排名都兩兩不同時，就完成了本題。
直接了解确實十分困難，是以下面結合圖再做說明。
下面進行代碼講解。
\(s\) 表示字元串。
\(sa_i\) 表示排名為 \(i\) 的字尾的編号。
首先，我們要先根據第一位排序，确定最初的 \(sa\)。
我們用 \(x_i\) 表示第一關鍵字。
倍增來了！！！
首先，定義 \(y_i\) 表示排名為第 \(i\) 的第二關鍵字。
然後根據上次排序的 \(sa\) 來确定 \(y\)。
确定完第一關鍵字和第二關鍵字，就可以更新 \(sa\) 了，更新方法跟開頭很像。
接下來就是要更新 \(x\) 了，要用到未更新的 \(x\) 和 \(sa\)。
先用暫時沒用的 \(y\) 來存此時的 \(x\)。
然後更新。
最後輸出。
模闆題