後綴數組 （Suffix Array）

0x00 Problems：

先來看一道題吧：後綴排序 - 題目

這是一道模板題，就是要對一個字元串的所有後綴進行排序，並且輸出排序好之後相鄰的後綴的LCP長度，後綴樹和後綴數組都可以，但是後綴樹構造太難懂（作者太傻），只好打後綴數組了。

------------------------------------------------------2016.6.10--------------------------------------------------------

再來一道水題 BZOJ 1031 。只要把原本的串複製兩份接起來，後綴排序即可。

0x01 Suffix Array：

首先，對於一個字元串 s，它的「後綴 i」表示「以下標為 i 開頭的後綴」。而後綴數組就是所有後綴按照字典序從小到大排序後的結果。

如何構造後綴數組呢？最簡單的就是快速排序一遍，這是極其暴力的，時間複雜度為。而倍增演算法就很好的利用了每個後綴之間的聯繫，在 時間內構造出後綴數組。

首先我們用基數排序求到每個字元串中的字元的名次。這裡我們就以aabaaaab為例，如圖：

第一輪之後的結果就是這樣。那麼第二輪，就是對每個後綴的前兩個字元進行排序。因為每個單字元的名次已經得出。就相當於對一個二元組（x，y）進行排序，且以 x 為第一關鍵字，以 y 為第二關鍵字。這麼排序之後就得到了這麼一幅圖：

接下來繼續倍增，對前四個字元進行排序，此時依舊相當於對一個二元組（x，y）排序，排序規則相同。此時的 x 和 y 分別表示前兩個字元的名次和第三、四個字元的名次（在第二次排序已經將其全部求出），所以同上進行排序，就能得到這樣的一幅圖：

這是我們可以發現每個後綴的名次已經完全不同，那麼此時就可以退出。本來是還需要倍增的，但因為已經完全不同，繼續倍增，結果也不會有變化。

那麼給出後綴數組構造的代碼：

gets(s); len = strlen(s);// 對後綴的第一個字元進行基數排序，m 表示名次的最大值。for (int i = 0; i < m; i++) buc[i] = 0; // buc 是一個桶for (int i = 0; i < len; i++) buc[x[i] = s[i]]++;for (int i = 1; i < m; i++) buc[i] += buc[i - 1];for (int i = len - 1; i >= 0; i--) SA[--buc[x[i]]] = i;for (int k = 1; k <= len; k <<= 1) { // k 倍增 int p = 0; // y[i] 用來表示名次為 i 的後綴(j + k) 的 j 。接下來直接用 SA 對第二關鍵字排序 for (int i = len - 1; i >= len - k; i--) y[p++] = i; // 後綴 len - k 及之後的所有後綴第二關鍵字最小。 for (int i = 0; i < len; i++) if (SA[i] >= k) y[p++] = SA[i] - k; // SA[i] >= k 表示改後綴出現在 k 之後，那麼就是第二關鍵字， // 且因為 SA 已排序好，這樣便可以通過這個排序出第二關鍵字。 for (int i = 0; i < m; i++) buc[i] = 0; for (int i = 0; i < len; i++) buc[x[y[i]]]++; for (int i = 1; i < m; i++) buc[i] += buc[i - 1]; for (int i = len - 1; i >= 0; i--) SA[--buc[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[SA[0]] = 0; // 重新計算每個一元的名次。 for (int i = 1; i < len; i++) { if (y[SA[i - 1]] == y[SA[i]] && y[SA[i - 1] + k] == y[SA[i] + k]) x[SA[i]] = p - 1; else x[SA[i]] = p++; } if (p >= len) break; // 每個後綴的名次已經完全不同，不需要繼續倍增 m = p; // 更新名次的最大值。}

那麼這樣我們就構造出了後綴數組。但本題還有一問，著我們要怎麼解決呢？就需要兩個輔助數組：rank[]，height[]。rank[i] 用來記錄後綴 i 在 SA 數組的位置。height[i] 記錄後綴 SA[i] 和 SA[i - 1] 的 LCP 的長度。

首先很容易求出 rank 數組：

for (int i = 0; i < len; i++) rank[SA[i]] = i;

如何計算 height 數組呢？最簡單的辦法，相鄰的兩個後綴硬求一遍 LCP 時間複雜度 ，有一種更加高效的方法，只需要 時間即可。先令一個輔助數組 h，其中 h[i] = height[rank[j]]。這裡有一個神奇的性質：.先來證明一下吧。

設排在後綴(i - 1)前一個的是後綴 k 。後綴(i - 1)和後綴 k 分別刪除首字母后得到的是後綴 i 和後綴(k + 1)。因為後綴 k 排在 後綴(i - 1)之前，所以後綴(k + 1) 必定也排在後綴 i 之前，並且它們的 LCP 長度為h[i - 1] + 1。很顯然，h[i - 1] - 1 是一系列 h 的最小值。包括排在後綴 i 之前的一個後綴 p 和 後綴 i 的 LCP 長度，即 h[i]。給出代碼：

for (int i = 0; i < len; i++) { if (rank[i] == 0) {height[0] = 0; continue;} // 第一個後綴的 LCP 為 0。 if (k) k--; // 從 k - 1 開始推 int j = SA[rank[i] - 1]; while (s[i + k] == s[j + k] && i + k < len && j + k < len) k++; height[rank[i]] = k;}

到這裡已經可以解決本題了。

0x02 後話

但其實後綴數組還有很多應用。

比如，可以通過對後綴數組的二分查找解決在線的多模版匹配問題。

還有，利用上述 height 數組可以利用 RMQ 來求出任意兩個後綴的 LCP。

正如評論中@後綴自動機·張 所說的，還是SAM穩啊！

比如 Problem - 4622

struct SuffixAutomaton { int to[N][30], fail[N], step[N]; int last, Tcnt, sum; int Q[N]; int Qcnt; int Extend(int key) { step[++Tcnt] = step[last] + 1; int p = last, u = Tcnt; memset(to[u], 0, sizeof to[u]); for (; !to[p][key]; p = fail[p]) to[p][key] = u; if (!p) { fail[u] = 1; } else { int q = to[p][key]; if (step[q] != step[p] + 1) { step[++Tcnt] = step[p] + 1; int v = Tcnt; memset(to[v], 0, sizeof to[v]); memcpy(to[v], to[q], sizeof to[q]); fail[v] = fail[q]; fail[q] = fail[u] = v; for (; to[p][key] == q; p = fail[p]) to[p][key] = v; } else { fail[u] = q; } } last = u; return sum += step[last] - step[fail[last]]; } void Init(char *S, int len) { Tcnt = last = 1; sum = 0; for(int i = 0; i < len; i++) Extend(S[i] - st); } inline void Print(void) { for (int i = 0; i < Qcnt; i++) putchar(Q[i] + st); puts(""); } void dfs(int u) { for (int i = 0; i < 26; i++) if (to[u][i]) { Q[Qcnt++] = i; Print(); dfs(to[u][i]); --Qcnt; } } void Debug(void) { Qcnt = 0; dfs(0); } void Clear(void) { Tcnt = last = 1; sum = 0; memset(to[1], 0, sizeof to[1]); }};

-----------------------------------------------------------完-----------------------------------------------------------