引子

眾所周知，寫(xiě)串串題是繞不開(kāi)后綴數(shù)據(jù)結(jié)構(gòu)的(有些時(shí)候還要上回文數(shù)據(jù)結(jié)構(gòu))

說(shuō)到后綴數(shù)據(jù)結(jié)構(gòu)，我就想起了后綴數(shù)組和后綴自動(dòng)機(jī)，對(duì)于后綴自動(dòng)機(jī)來(lái)講，大家常用的構(gòu)建算法是O(nΣ)的，如果使用map存儲(chǔ)轉(zhuǎn)移邊，那么復(fù)雜度可以降到O(nlogΣ),使用動(dòng)態(tài)擴(kuò)張的hash表，理論上我們可以做到O(n)的期望復(fù)雜度，但是實(shí)際應(yīng)用的時(shí)候相當(dāng)吃hash函數(shù)而且常數(shù)也不小

但是對(duì)于后綴數(shù)組來(lái)講，最常見(jiàn)的寫(xiě)法是大常數(shù)O(nlogn)的倍增法，這導(dǎo)致后綴數(shù)組經(jīng)常被人扣上復(fù)雜度高的帽子，甚至有毒瘤出題人惡意開(kāi)大數(shù)據(jù)范圍來(lái)卡后綴數(shù)組……

我們也有一個(gè)DC3算法可以在O(n)的時(shí)間內(nèi)構(gòu)造后綴數(shù)組，但是想必大家剛學(xué)后綴數(shù)組的時(shí)候就被告知這個(gè)算法常數(shù)極大實(shí)現(xiàn)復(fù)雜不太適合當(dāng)板子背

那么有沒(méi)有一個(gè)實(shí)現(xiàn)簡(jiǎn)單，效率高常數(shù)小的后綴數(shù)組構(gòu)建算法可以幫后綴數(shù)組洗掉復(fù)雜度高常數(shù)大的帽子呢？，答案是有的，就是sais算法

SA-IS

這個(gè)算法的名字大概是Suffix-Array-Induce-Sort的意思，induce sort指的是一種被稱之為誘導(dǎo)排序的算法也是這個(gè)算法的精髓

sais算法的精髓在于它比較后綴的方式，它根據(jù)兩個(gè)后綴首字母是否相同來(lái)比較兩個(gè)后綴

如果兩個(gè)后綴(i,j)的首字母不同，那么兩個(gè)后綴可以直接比較，否則我們可以將兩個(gè)后綴刪掉他們的首字母遞歸比較(i+1,j+1)這兩個(gè)后綴的大小

在接下來(lái)的敘述當(dāng)中我們認(rèn)為我們處理的字符串是字符數(shù)組a,a[i]表示字符串a(chǎn)的第i個(gè)字符

S型后綴和L型后綴

為了方便我們推導(dǎo)各種各樣的性質(zhì)我們先把一個(gè)字符串的后綴分成兩類,S型后綴和L型后綴，并且為了規(guī)避各種各樣的分情況討論，我們?cè)谧址暮竺嫘枰右粋€(gè)哨兵字符“#”

S型后綴和L型后綴的定義也很簡(jiǎn)單

'#'是一個(gè)S型后綴

如果后綴i比i+1小i就是S型后綴，否則就是L型后綴

那么這個(gè)定義有什么用呢？根據(jù)這個(gè)定義我們可以得到兩個(gè)神奇的結(jié)論

結(jié)論1：若a[i]和a[i+1]相同，則后綴i和后綴i+1的類型相同

證明很簡(jiǎn)單，兩個(gè)后綴(i,i+1)的首字母相同，顯然要去遞歸的比較(i+1,i+2),那么(i,i+1)和(i+1,i+2)的大小關(guān)系是相同的，自然類型也就一致了

根據(jù)這個(gè)結(jié)論我們可以倒著掃一遍字符串確定所有后綴的類型

結(jié)論2:若a[i]和a[j]相同且i是S型后綴j是L型后綴,則i比j大

還是那個(gè)思想，首字母相同了要去遞歸的比較(i+1,j+1)

由于我們知到i是一個(gè)S型后綴而j是一個(gè)L型后綴，那么我們可以很快的推出a[i+1] ≥ a[i],a[j+1] ≤ a[j],所以說(shuō)除非a[i+1]=a[i]=a[j+1]=a[j]，我們都能得到i比j大的結(jié)論,

而a[i+1]=a[j+1]的時(shí)候我們可以接著首字母刪去遞歸下去，這樣我們的結(jié)論就成立了

誘導(dǎo)排序(induce sort)

sais的核心是誘導(dǎo)排序，但是誘導(dǎo)排序的正確性是基于歸納法證明的.所以這個(gè)算法不太好理解，它很簡(jiǎn)單，但是你可能理解不了為什么它是對(duì)的

根據(jù)我們推出來(lái)的結(jié)論我們可以知道，在后綴數(shù)組當(dāng)中首字母相同的后綴排成了連續(xù)的一段;而首字母相同的后綴里面,前面全部是L型的后綴后面全部是S型的后綴

那么我們想個(gè)辦法,先把所有L型后綴排好,再把所有的S型后綴排好,這樣就可以把所有的后綴排好序了

那么我們來(lái)考慮一下怎么把所有的L型后綴排好序，那么我們還是采用這樣的方式來(lái)比較大小

如果兩個(gè)L型后綴(i,j)的首字母不一樣那么可以直接比較，否則我們遞歸的比較(i+1,j+1)

那么我們倒著想，假設(shè)我們已經(jīng)有了一部分后綴的大小關(guān)系，然后我們每次取出手頭已有的最小后綴i，執(zhí)行這樣一個(gè)操作，如果i-1是一個(gè)L型后綴,那么把i-1加入我們的集合，重復(fù)這個(gè)過(guò)程若干次，我們就能得到一部分L型后綴的大小關(guān)系

如果用堆來(lái)維護(hù)剛才的過(guò)程，復(fù)雜度帶log無(wú)法接受，但是我們有一個(gè)巧妙的做法可以完成上述過(guò)程

我們直接維護(hù)sa數(shù)組，先處理出一個(gè)cnt數(shù)組表示首字母為i的后綴從sa數(shù)組的哪里結(jié)束(和你倍增法基數(shù)排序的時(shí)候原理很像),之后把sa數(shù)組全部初始化為-1

然后把我們倒著掃一遍手頭里已經(jīng)有的后綴全部插入到sa數(shù)組對(duì)應(yīng)的位置(操作方式和倍增法的基排是一樣的)

接下來(lái)我們從左向右掃一遍sa數(shù)組，如果第i位比1大并且sa(i-1)是一個(gè)L型后綴，我們就把L型后綴插入到對(duì)應(yīng)的位置上

(你可以把插入的過(guò)程理解為將sa數(shù)組按照首字母劃分為若干個(gè)桶，然后將這個(gè)后綴push到對(duì)應(yīng)的桶里去，代碼上寫(xiě)起來(lái)和倍增法的基排沒(méi)啥區(qū)別）

如此這般我們就可以在O(n)的時(shí)間內(nèi)完成上述算法

如果我們一開(kāi)始掌握的信息足夠多，比如說(shuō)我們知道了全部的S型后綴排序結(jié)果，那么我們就可以用上面的算法還原出所有L型后綴的排序結(jié)果，原理很簡(jiǎn)單，在剛才的算法當(dāng)中，每一個(gè)L型后綴i都是被后綴i+1加入的，因?yàn)槭荓型，所以在sa數(shù)組當(dāng)中i肯定在i+1后面，所以沒(méi)有一個(gè)L型后綴會(huì)被漏掉

接下來(lái)我們需要證明的就是對(duì)于任意的兩個(gè)L型后綴i和j，如果i比j小那么i肯定比j先加入

證明如下:如果i和j的首字母不同那么i和j被分在了不同的桶里，大小關(guān)系一目了然，否則兩個(gè)后綴的大小關(guān)系依賴于被塞到桶里的時(shí)間，也就是依賴于(i+1,j+1)的大小關(guān)系，符合我們遞歸比較的原理

同理我們知道了全部的L型后綴的排序結(jié)果，我們只需要把剛才的算法中的正序掃描改成倒序掃描就可以還原S型后綴的全部信息

這樣只要我們一開(kāi)始掌握的后綴的大小信息無(wú)誤并且足夠的多，我們就能正確的還原出一個(gè)有序的sa數(shù)組，具體點(diǎn)，我們知道了關(guān)于S型的大小信息可以生成L型后綴的信息，知道了L型后綴的信息也可以還原出S型后綴的所有信息

遞歸,lms子串與lms后綴

誘導(dǎo)排序算法允許我們從L型后綴誘導(dǎo)到S型后綴上，也允許我們從S型后綴誘導(dǎo)到L型后綴上，但是我們從S型后綴誘導(dǎo)到L型后綴的時(shí)候并不需要全部的S型后綴的大小信息，相反，我們僅僅需要一部分S型后綴的信息照樣可以還原出L型后綴的信息

把誘導(dǎo)排序算法的正確性證明念一遍，我們會(huì)發(fā)現(xiàn)關(guān)鍵在于遞歸比較(i+1,j+1)的大小關(guān)系這一段，如果i和j都是L型后綴，我們不能保證(i+1,j+1)都是L型后綴

但是倒過(guò)來(lái)看，我們也僅僅需要那些左邊就是L型后綴的S型后綴的大小信息了

我們?cè)谶@里稱一個(gè)后綴為lms(Left-Most-Suffix)后綴當(dāng)且僅當(dāng)這個(gè)后綴左邊是L型后綴而它本身是一個(gè)S型后綴，根據(jù)這個(gè)定義，還原所有的L型后綴的排序關(guān)系僅僅需要所有l(wèi)ms后綴的大小關(guān)系

那么我們可以把剛才的誘導(dǎo)排序算法升級(jí)一下，我們先搞出來(lái)所有l(wèi)ms后綴的大小關(guān)系，然后當(dāng)做'種子'生成L型后綴的大小關(guān)系，然后從L型后綴的大小關(guān)系反過(guò)來(lái)生成S型后綴的大小關(guān)系，如此這般我們就從lms后綴的排序結(jié)果誘導(dǎo)出了我們想要的后綴數(shù)組

那么一個(gè)顯然的事實(shí)是長(zhǎng)度為n的字符串最多有\(zhòng)frac{n}{2}個(gè)lms后綴，如果我們可以想辦法將這個(gè)問(wèn)題遞歸下去,我們就可以得到一個(gè)復(fù)雜度滿足以下遞歸式的算法

T(n)=T(n/2)+O(n)=O(n)

那么問(wèn)題來(lái)了我們?cè)趺催f歸問(wèn)題呢？答案是用lms子串

我們定義lms子串表示從左向右數(shù)第i個(gè)lms后綴和第i+1個(gè)lms后綴之間的字符串

給個(gè)例子:

對(duì)于字符串“mmiissiissppii“來(lái)講，lms子串指的就是[3,7],[7,11],[11,17]這三個(gè)子串

注意相鄰的兩個(gè)lms子串會(huì)重疊一個(gè)字符

那么我們的遞歸方法是，將lms子串離散化之后按順序拼起來(lái)形成一個(gè)新的字符串，比如說(shuō)在上面的例子當(dāng)中我們會(huì)得到一個(gè)字符串“221”，

那么我們這里有一個(gè)結(jié)論是對(duì)于原串的兩個(gè)lms后綴p1,p2,如果
p1是從左向右數(shù)的第i個(gè)lms后綴，p2是從左向右數(shù)的第j個(gè)lms后綴,那么我們比較這兩個(gè)后綴的大小可以轉(zhuǎn)化為比較新字符串上i和j這兩個(gè)后綴的大小

看起來(lái)挺顯然的，不就是把一塊字符縮成了一個(gè)字符嘛……

但是其實(shí)并沒(méi)有我們想的那么顯然，我們接下來(lái)會(huì)嚴(yán)謹(jǐn)?shù)淖C明為什么剛才的結(jié)論是對(duì)的

首先先明確一下比較lms子串的規(guī)則，我們比較兩個(gè)lms子串的時(shí)候?qū)τ诿恳粋€(gè)字符同時(shí)比較字符的字典序大小和所在位置后綴的SL類型,舉個(gè)例子，我們認(rèn)為(a,S)和(a,L)是不相等的，盡管字符一樣但是所在位置的S和L類型卻不一樣，同時(shí)我們認(rèn)為S類型大于L類型

假設(shè)我們有兩個(gè)lms后綴p1,p2,現(xiàn)在我們想要比較兩個(gè)后綴的大小，我們可以根據(jù)兩個(gè)后綴在新字符串上第一位的字符(不妨設(shè)為第i位和第j位)是否相等來(lái)進(jìn)行分情況討論

case1:第一位的字符是相等的

我們發(fā)現(xiàn)新字符串上兩個(gè)字符相等,等價(jià)于原來(lái)字符串上兩個(gè)lms子串相等，那么既然兩個(gè)lms子串相等了那么這兩個(gè)子串的長(zhǎng)度len必然是一樣的，因此我們可以將兩個(gè)后綴同時(shí)去掉長(zhǎng)度為len-1的部分遞歸比較剩下的部分，在新字符串上也就是遞歸到了第i+1位和第j+1位，符合我們字符串比較的邏輯

case2:第一位的字符是不等的

那么你可能會(huì)說(shuō):既然新字符串的兩個(gè)字符都不一樣了，就說(shuō)明在原來(lái)的字符串上肯定有不一樣的位，所以這種情況是顯然的

那好像我們忽視了一種情況哎，兩個(gè)lms子串代表的字符不一樣是因?yàn)槠渲幸粋€(gè)是另一個(gè)的前綴

這種情況下我們的算法就會(huì)鍋掉，因?yàn)閮蓚€(gè)后綴明明沒(méi)有分出大小我們就強(qiáng)行欽定一個(gè)大于另一個(gè)了

事實(shí)果真如此嗎？

答案是這種情況不存在，我們比較lms子串的規(guī)則是同時(shí)比較字符和SL類型的后綴，在這種情況下不存在一個(gè)lms子串是另一個(gè)的前綴，因?yàn)橐粋€(gè)lms子串的SL類型必須是形如SSSSLLLLS這樣的，前面是一串S中間是一串L，最后是恰好一個(gè)S，那么我們發(fā)現(xiàn)如果一個(gè)是另一個(gè)的前綴，兩個(gè)串必然會(huì)在短的字符串的結(jié)尾處SL類型不匹配，從而不存在這種情況

那么此時(shí)我們就可以放心大膽把所有l(wèi)ms子串進(jìn)行離散化，然后遞歸進(jìn)行sais算法了，看起來(lái)我們得到了一個(gè)優(yōu)秀的O(n)算法？

離散化lms子串與誘導(dǎo)排序

現(xiàn)在我們只差最后一步就能實(shí)現(xiàn)完整的sais算法了，也就是離散所有的lms子串的過(guò)程

如果我們實(shí)現(xiàn)這一步使用的是基數(shù)排序那么我們將會(huì)得到傳說(shuō)中的KA-algorithm，但是這東西很慢啊……我們想想有沒(méi)有什么優(yōu)秀的排序做法

答案還是誘導(dǎo)排序，傳統(tǒng)的誘導(dǎo)排序要求我們傳一個(gè)有序的lms后綴數(shù)組進(jìn)去，但是現(xiàn)在我們可以亂序傳入lms后綴數(shù)組，當(dāng)然誘導(dǎo)排序會(huì)返回一個(gè)錯(cuò)誤的結(jié)果，

但是我們斷言，在返回的后綴數(shù)組當(dāng)中關(guān)于lms后綴的子序列是按照每個(gè)lms后綴開(kāi)頭的lms子串為關(guān)鍵字進(jìn)行排序的

具體點(diǎn)來(lái)講依然使用歸納法證明算法正確性

我們知道初始的時(shí)候的lms數(shù)組是亂的，因此歸納的初始條件直接被打破了

但是如果我們換個(gè)命題進(jìn)行歸納呢？

我們一開(kāi)始傳進(jìn)去的lms數(shù)組，如果只看開(kāi)頭的第一個(gè)字母，在后綴數(shù)組當(dāng)中是有序的

那么在第一輪誘導(dǎo)過(guò)后，對(duì)于每個(gè)L型后綴，如果只看這個(gè)后綴的開(kāi)頭到第一個(gè)S型字符位置的位置，他們也是有序的

在第二輪誘導(dǎo)過(guò)后，對(duì)于每個(gè)S型后綴，它們有序的部分恰好是這個(gè)后綴的開(kāi)頭到第一個(gè)lms字符所在的位置，如果這個(gè)后綴是一個(gè)lms型后綴那么這個(gè)后綴有序的部分是這個(gè)后綴開(kāi)頭的lms字符

所以我們證明了只需要再來(lái)一輪誘導(dǎo)排序就可以給所有l(wèi)ms子串排好序，然后我們就可以很輕松的完成離散化啦~

至此我們完成了SA-IS算法的最后一塊拼圖，此時(shí)我們已經(jīng)可以嘗試實(shí)現(xiàn)sais算法了~

實(shí)現(xiàn)

由于sais算法的實(shí)現(xiàn)難度不小(主要是如何避免冗余代碼上)，這里給出一個(gè)范例代碼和簡(jiǎn)略的注釋

實(shí)際上實(shí)現(xiàn)精妙的話sais算法的代碼量相當(dāng)小，甚至和倍增法差不多

(基本是抄的uoj的這份提交記錄)

/******************************************
這里的誘導(dǎo)排序函數(shù)由于需要傳非常多的參數(shù)，所以使用了宏的方式來(lái)實(shí)現(xiàn)了一個(gè)函數(shù)
具體的實(shí)現(xiàn)方式可以看下面的inds(lms)這個(gè)宏
由于多行宏旁邊寫(xiě)不了注釋我會(huì)在行上面寫(xiě)注釋

sais的算法流程 :

1.確定每個(gè)后綴的類型

2.確定第i個(gè)lms后綴的編號(hào)以及編號(hào)為i的后綴是第幾個(gè)lms后綴

3.進(jìn)行一次誘導(dǎo)排序給lms子串排序

4.掃描一遍得到的sa數(shù)組，生成用于遞歸的字符串

5.如果新字符串中的每一個(gè)字符都不同，后綴數(shù)組可以直接計(jì)算，此處不遞歸

6.否則遞歸進(jìn)行一次sais

7.根據(jù)之前記錄了第i個(gè)lms后綴的編號(hào)和返回的后綴數(shù)組計(jì)算lms后綴的順序

8.進(jìn)行一次誘導(dǎo)排序并返回

******************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
template <typename T>
inline void gm(T*& bas, int siz, T*& op) {
    op = bas;
    bas += siz;// 這里把內(nèi)存提前申請(qǐng)好然后用指針?lè)峙鋬?nèi)存
}
//這里sum表示桶的位置，cur是sum的一份copy，避免每次都要做前綴和
// S型后綴的桶是倒著開(kāi)的也要倒著掃，L型后綴的桶的是正著開(kāi)的也要正著掃
#define pus(x) (sa[cur[a[x]]--] = x)  // 插入S型后綴
#define pul(x) (sa[cur[a[x]]++] = x)  //插入誘導(dǎo)排序
//誘導(dǎo)排序的宏，進(jìn)行了兩輪誘導(dǎo)過(guò)程:分別是從lms誘導(dǎo)到L和從L誘導(dǎo)到S
#define inds(lms)                                         \
    for (int i = 1; i <= n; i++) sa[i] = -1;              \
    for (int i = 1; i <= n; i++) sum[i] = 0;              \
    for (int i = 1; i <= n; i++) sum[a[i]]++;             \
    for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];    \
    for (int i = 1; i <= n; i++) cur[i] = sum[i];         \
    for (int i = m; i >= 1; i--) pus(lms[i]);             \
    for (int i = 1; i <= n; i++) cur[i] = sum[i - 1] + 1; \
    for (int i = 1; i <= n; i++)                          \
        if (sa[i] > 1 && !tp[sa[i] - 1])                  \
            pul(sa[i] - 1);                               \
    for (int i = 1; i <= n; i++) cur[i] = sum[i];         \
    for (int i = n; i >= 1; i--)                          \
        if (sa[i] > 1 && tp[sa[i] - 1])                   \
            pus(sa[i] - 1);
int sa[N];
int sum[N];
int cur[N];
int rk[N];
int A_bas[N << 4];
int* A_t;
inline void sais(int n, int* a) {
    int* tp;             //現(xiàn)開(kāi)數(shù)組現(xiàn)分配內(nèi)存
    gm(A_t, n + 1, tp);
    int* p;
    gm(A_t, n + 2, p);
    tp[n] = 1;
    //倒著掃一遍確定后綴類型
    for (int i = n - 1; i >= 1; i--) tp[i] = (a[i] == a[i + 1]) ? tp[i + 1] : (a[i] < a[i + 1]);
    //確定第i個(gè)lms后綴的編號(hào)和編號(hào)為i的后綴是第幾個(gè)lms后綴
    int m = 0;
    for (int i = 1; i <= n; i++) rk[i] = (tp[i] && !tp[i - 1]) ? (p[++m] = i, m) : -1;
    //進(jìn)行一輪誘導(dǎo)排序，生成新的字符串
    inds(p);
    int tot = 0;
    int* a1;
    gm(A_t, m + 1, a1);
    p[m + 1] = n;
    //掃一遍對(duì)lms子串進(jìn)行離散化
    for (int i = 1, x, y; i <= n; i++)
        if ((x = rk[sa[i]]) != -1) {
            if (tot == 0 || p[x + 1] - p[x] != p[y + 1] - p[y]) //如果長(zhǎng)度不一致顯然不等
                tot++;
            //否則暴力for一遍比較兩個(gè)lms串是否相等
            else
                for (int p1 = p[x], p2 = p[y]; p2 <= p[y + 1]; p1++, p2++)
                    if ((a[p1] << 1 | tp[p1]) != (a[p2] << 1 | tp[p2])) {
                        tot++;
                        break;
                    }
            a1[y = x] = tot;
        }
    if (tot == m)
        for (int i = 1; i <= m; i++) sa[a1[i]] = i; //如果字符互不相同就直接計(jì)算后綴數(shù)組，否則遞歸
    else
        sais(m, a1);
    for (int i = 1; i <= m; i++) a1[i] = p[sa[i]]; //還原lms子串的順序，進(jìn)行誘導(dǎo)排序
    inds(a1);
}
char mde[N];
int n;
int a[N];
int tr[300];
char buf[20];
int cnt;
int main() {
    A_t = A_bas;
    scanf('%s', mde + 1);
    while (mde[n + 1] != '\0') n++;
    for (int i = 1; i <= n; i++) tr[mde[i]] = 1;
    for (int i = 1; i < 300; i++) tr[i] += tr[i - 1];
    for (int i = 1; i <= n; i++) a[i] = tr[mde[i]] + 1;
    a[++n] = 1;
    sais(n, a);
    for (int i = 2; i <= n; i++) {
        int tmp = sa[i];
        while (tmp) buf[++cnt] = tmp % 10 + 48, tmp /= 10;
        while (cnt) putchar(buf[cnt--]);
        putchar(' ');
    }
    return 0;  //拜拜程序~
}

例題

大部分時(shí)候后綴數(shù)組都需要套數(shù)據(jù)結(jié)構(gòu)所以用到O(n)后綴數(shù)組的時(shí)候不多……

但是不能說(shuō)沒(méi)有這種題啊，比如說(shuō)這道題

codeforcesgym102114 J Just So You know

一句話題意是求一個(gè)字符串所有子串的哈夫曼樹(shù)代價(jià)和

那么我們可以借助SAIS算法O(n)構(gòu)建后綴樹(shù)，統(tǒng)計(jì)出每個(gè)子串出現(xiàn)了多少次，由于出現(xiàn)次數(shù)小于n的節(jié)點(diǎn)的權(quán)值只有O(n)種，而權(quán)值大于n的節(jié)點(diǎn)的數(shù)目不超過(guò)O(n)，那么對(duì)于前面一種節(jié)點(diǎn)我們拿數(shù)組存，后面一種節(jié)點(diǎn)拿隊(duì)列維護(hù)一下就可以做到線性的復(fù)雜度了~

這里是代碼~

還有一個(gè)例題就是P5112

雖然說(shuō)這題可以拿hash或者后綴自動(dòng)機(jī)搞過(guò)去，但是使用SAIS的后綴數(shù)組應(yīng)該是這題最快的穩(wěn)定做法了(畢竟hash是一個(gè)不穩(wěn)定做法，很容易被卡住)，想練手的同學(xué)可以嘗試著寫(xiě)一寫(xiě)這題