構造后綴數組

我們會得到兩個數組 \(sa_i\) 表示排名為 \(i\) 的后綴是哪一個，\(rk_i\) 表示后綴 \(i\) 的排名。

這里只講倍增做法。

原理非常簡單，如下圖：

實現需要一個對兩位關鍵字進行排序的基數排序，設 \(y_i\) 表示按照第二維關鍵字排序，排名為 \(i\) 的是哪一個位置。設 \(rk_i\) 表示第 \(i\) 個位置，第一維關鍵字排序，排名是多少。

我們按照 \(i\) 從小到大把 \(rk_{y_i}\) 加入我們的桶中（我們用桶排來實現），對桶做前綴和之后，從大到小枚舉 \(n\)，按照 \(rk_{y_i}\) 來重新計算每個位置的排名。

這樣做正確性顯然，考慮如果兩個位置第二維關鍵字排名不同，而第一維相同，那么排名越大的會先被枚舉到，導致排名變大。如果第一維就不同，那么第一維更優的顯然會排名更小。

所以就可以簡單構造了，具體代碼請到代碼倉庫。

求 height

LCP 的定義是最長公共前綴，以下用 \(LCP(i,j)\) 表示編號為 \(i\) 的后綴和編號為 \(j\) 的后綴的 LCP，我們令 \(Height_i=LCP(sa_i,sa_{i-1})\)，而 \(Height_1\) 可以視作 \(0\)。我們考慮如何求 \(Height\) 數組。

• 引理：\(Height_{rk_i}\ge Height_{rk_{i-1}}-1\)。

證明：如果 \(Height_{rk_{i-1}-1}\) 小于等于 \(1\)，那么上面這個式子顯然成立，這是因為 \(Height_i\ge 0\)。

如果 \(Height_{rk_{i-1}-1}>1\)，我們考慮設后綴 \(i-1\) 為 \(aAD\)，那么后綴 \(i\) 就是 \(AD\)，其中 \(A\) 是一個長度為 \(Height_{rk_{i-1}}-1\) 的字符串，由于 \(Height\) 數組的定義，我們考慮后綴 \(sa_{rk_{i-1}-1}\) 這個字符串一定是 \(aAB\) 的形式，所以 \(sa_{rk_{i-1}-1}+1\) 這個后綴一定是 \(AB\) 的形式，所以這個后綴一定排在后綴 \(i\) 的前面，所以我們可以知道 \(Height_{rk_i-1}\) 一定包含字符串 \(A\)，所以結論成立。

我們利用上面這個東西就可以 \(O(n)\) 的來求 \(Height\) 數組了。

有一個結論是 \(LCP(sa_i,sa_j)=\min_{i+1\le k\le j}Height_k\)，這個可以感性理解一下，如果 \(Height\) 一直大于某個值，那么這一段就一直有，反之，肯定是在一個后綴中改變。