后綴數組

后綴數組 (SA) 是一種重要的數據結構，通常使用倍增或者DC3算法實現，這超出了我們的討論范圍。
在本題中，我們希望使用快排、Hash與二分實現一個簡單的O(nlog2n)的后綴數組求法。
詳細地說，給定一個長度為 n 的字符串S（下標 0~n-1），我們可以用整數 k(0≤k<n) 表示字符串S的后綴 S(k~n-1)。
把字符串S的所有后綴按照字典序排列，排名為 i 的后綴記為 SA[i]。
額外地，我們考慮排名為 i 的后綴與排名為 i-1 的后綴，把二者的最長公共前綴的長度記為 Height[i]。
我們的任務就是求出SA與Height這兩個數組。

輸入格式
輸入一個字符串，其長度不超過30萬。
字符串由小寫字母構成。

輸出格式
第一行為數組SA，相鄰兩個整數用1個空格隔開。
第二行為數組Height，相鄰兩個整數用1個空格隔開，我們規定Height[1]=0。

輸入樣例：
ponoiiipoi
輸出樣例：
9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

---

說實話看到這道題的時候真的是一臉懵，這東西咋用hash，二分，快排。
后來找了些博客看，終于理解其中的思路了，
一、先記錄整條的hash值。
二、用一個sort函數，自定義cmp。
三、通過二分確定兩個后綴字符之間的前綴相同字母。
這道題寫這篇題解的時候又重新去寫了一遍，感覺真的難。

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; typedef unsigned long long ull; const int base = 131; const int N = 3e5 + 10; char str[N]; ull h[N], p[N]; int sa[N], n; ull gethash(int l, int r) {//得到某一段的hash值return h[r] - h[l - 1] * p[r - l + 1]; } int sumsub(int a, int b) {int l = 0, r = min(n - a + 1, n - b + 1);//取最小的。while(l < r) {//二分。int mid = (l + r + 1) >> 1;if(gethash(a, a + mid - 1) != gethash(b, b + mid - 1)) r = mid - 1;else l = mid;}return r; } bool cmp(int a, int b) {int l = sumsub(a, b);//兩個的相同前綴長度。int x = a + l > n ? - 1e9 : str[a + l];如果有一個單詞都是前綴，防止發生數組越界。int y = b + l > n ? - 1e9 : str[b + l];return x < y; } int main() {scanf("%s", str + 1);//從第一個字符開始可以避免hash的邊界問題。n = strlen(str + 1);p[0] = 1;for(int i = 1; i <= n; i++) {h[i] = h[i - 1] * base + str[i] - 'a' + 1;p[i] = p[i - 1] * base;sa[i] = i;}sort(sa + 1, sa + n + 1, cmp);//對下標進行排序。for(int i = 1; i <= n; i++) printf("%d%c", sa[i] - 1, i == n ? '\n' : ' ');printf("0 ");for(int i = 2; i <= n; i++) printf("%d%c", sumsub(sa[i], sa[i - 1]), i == n ? '\n' : ' ');return 0; }

這個算法耗時還是非常長的，并不是真正的能用的算法，但是這個寫法的綜合力度還是比較高的，思想還是可以借鑒的。

總結

以上是生活随笔為你收集整理的算法竞赛进阶指南——后缀数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。