【參考博客】

https://xminh.github.io/2018/02/27/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84-%E6%9C%80%E8%AF%A6%E7%BB%86(maybe)%E8%AE%B2%E8%A7%A3.html

?

?

---

?

【定義】

?

【后綴】從第i位到字符串結(jié)尾的子串

??

---

【解決問題】

?

從而解決

...................在字符串中找子串

...................比較子串關(guān)系

...................查找不同子串的數(shù)目

?

一般來說都是解決

字符串和子串關(guān)系的問題

?

---

?

【算法學(xué)習(xí)】

?

后綴數(shù)組能夠在 nlogn的時(shí)間復(fù)雜度內(nèi)求取出以下數(shù)組

?

【注意】明白字符串包含字符的范圍?

?

SA [] 儲(chǔ)存，第 i 個(gè)數(shù)字表示的是字典序第 i 大的后綴是以 SA_i 開始的后綴

即? ?“排第幾的是哪個(gè)后綴”

rank [] 儲(chǔ)存，從第i位開始的后綴的字典序排名是 i

即? ?“某個(gè)后綴排第幾個(gè)”?

?

對(duì)SA的求取，我們可以看作對(duì)所有的后綴進(jìn)行排序

而這個(gè)排序顯然如果直接莽的話肯定T，所以我們需要另外一種方法

?

這里使用基數(shù)排序+倍增的方法進(jìn)行優(yōu)化

?

將所有的后綴進(jìn)行排序得到SA，這是我們的目的

?

基數(shù)排序，是對(duì)兩個(gè)關(guān)鍵字的元素進(jìn)行排序從而達(dá)到線性復(fù)雜度的方法

顯然，在當(dāng)兩個(gè)后綴第一個(gè)字符相等的情況下，我們不可避免的去用第二個(gè)字符進(jìn)行比較

這里我們需要注意到一個(gè)事情

第 i 個(gè)后綴的第二個(gè)字符是第 i + 1 的第一個(gè)字符

那這和直接莽好像沒有什么區(qū)別？

?

?

所以我們就用到了倍增，每次確定后綴的以前 2 ^ k 長度的字符串排序的順序

然后通過這個(gè)，就能夠求出 2 ^ ( k + 1 ) 長度的后綴的前綴

通過，第 i 位的和第 i + k 位的，于是就能求出來

?

因?yàn)榈谝粋€(gè)字符有可能一樣，導(dǎo)致有兩個(gè)后綴排名相等

所以總排名數(shù)和后綴長度不同

所以長度為2時(shí)同理

而當(dāng)所有總排名和后綴長度相同時(shí)，這個(gè)時(shí)候就找到了所有

?

下面是對(duì)使用到的各個(gè)數(shù)組的意義的描述：

c[] 桶，記錄第 i 位的元素有多少個(gè)

x[] 后綴 i 的第一關(guān)鍵字，所以最開始是等于第 i 位字符

y[] 第二關(guān)鍵字排名第 i 的字符串，第一關(guān)鍵字的位置

?

【代碼】

?首先求出所需要的幾個(gè)數(shù)組的初值

//初始化int n = strlen(s+1);int m = 128;//m只需要大于 ascii（‘z'）即可//因?yàn)榈谝徊讲⒉恢劳暗囊?guī)模for (int i = 1; i <= n; i++)++c[x[i] = s[i]];//計(jì)算每一個(gè)字符的數(shù)量，同樣的放在一起for (int i = 2; i <= m; i++)c[i] += c[i - 1];//求前綴和for (int i = n; i >= 1; i--) SA[c[x[i]]--] = i;//從后往前，這樣就能求出最開始順序

倍增的同時(shí)進(jìn)行排序

for (int k = 1; k <= n; k <<= 1) //k是之前提到的，每次枚舉的字符串長度 {int num = 0;for (int i = n - k + 1; i <= n; i++) y[++num] = i;//先將最后的幾個(gè)去掉for (int i = 1; i <= n; i++)if (SA[i] > k)y[++num] = SA[i] - k;//當(dāng)這個(gè)位置的后綴在長度之外時(shí)//將這個(gè)位置的字符放到第二關(guān)鍵字中for (int i = 1; i <= m; i++)c[i] = 0;//清空桶for (int i = 1; i <= n; i++)c[x[i]]++;//放入第一關(guān)鍵字//第一關(guān)鍵字是已經(jīng)算好的//第一次是初始化時(shí)計(jì)算好的//第二次的計(jì)算過程在下面for (int i = 2; i <= m; i++)c[i] += c[i - 1];//和初始化一樣的求前綴和for (int i = n; i >= 1; i--)SA[c[x[y[i]]]--] = y[i], y[i] = 0;//在保證第一關(guān)鍵字的同時(shí)使用第二關(guān)鍵字排序//從后往前，第二關(guān)鍵字靠后的會(huì)被先剔除掉//考慮下數(shù)組的操作 swap(x, y);//這里是為了保存上一步得到的y，沒有太多其他意思x[SA[1]] = 1; num = 1;for (int i = 2; i <= n; i++)x[SA[i]] =(y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ?//這里注意回憶SA的意義//比較的是和其排名相近的元素，也是最有可能兩個(gè)關(guān)鍵字都相同的元素//當(dāng)字符的第二關(guān)鍵字，前后都相同時(shí)//說明沒有新的元素，所以不加//如果有，則加 ？ num : ++num;if (num == n) break;m = num;}

?

---

?

【模板題】

?

【luogu P3809】

求一個(gè)字符串的SA

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 1000010; char s[MAXN]; int SA[MAXN]; int x[MAXN], c[MAXN], y[MAXN]; void get_SA(char *s) {//初始化int n = strlen(s + 1);int m = 128;for (int i = 1; i <= n; i++)++c[x[i] = s[i]];//計(jì)算每一個(gè)字符的數(shù)量，同樣的放在一起for (int i = 2; i <= m; i++)c[i] += c[i - 1];//求前綴和for (int i = n; i >= 1; i--)SA[c[x[i]]--] = i;//從后往前，這樣就能求出最開始順序for (int k = 1; k <= n; k <<= 1){int num = 0;for (int i = n - k + 1; i <= n; i++) y[++num] = i;//把最后幾個(gè)字符放進(jìn)去for (int i = 1; i <= n; i++)//按照順序遍歷if (SA[i] > k)//如果長度大于ky[++num] = SA[i] - k;//把第一個(gè)放進(jìn)去for (int i = 1; i <= m; i++)c[i] = 0;for (int i = 1; i <= n; i++)c[x[i]]++;//x[i]是第一關(guān)鍵字for (int i = 2; i <= m; i++)c[i] += c[i - 1];//求前綴和for (int i = n; i >= 1; i--)SA[c[x[y[i]]]--] = y[i], y[i] = 0;swap(x, y);x[SA[1]] = 1; num = 1;for (int i = 2; i <= n; i++)x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? num : ++num;if (num == n) break;m = num;}return; } int main() {scanf("%s", s + 1);get_SA(s);int n = strlen(s + 1);for (int i = 1; i <= n; i++)printf("%d ", SA[i]);return 0; } View Code

?

?

---

【擴(kuò)展】

?

LCP/height數(shù)組的求取

?

轉(zhuǎn)載于:https://www.cnblogs.com/rentu/p/11331536.html

總結(jié)

以上是生活随笔為你收集整理的算法学习：后缀数组（SA）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。