Mato is No.1

【后綴數(shù)組真難懂啊啊……就20+行的代碼搞了幾天才理解……不知是不是我太沙茶了】

【1】一些定義：
字符串：廣義的字符串是指“元素類型有序，且元素值有一定范圍的序列”，其元素不一定非要是字符，可以是數(shù)字等，因此整數(shù)、二進(jìn)制數(shù)等也是字符串；
字符集：字符串的元素值的范圍稱為字符集，其大小記為SZ。
字符串的長度：字符串中元素的個(gè)數(shù)，一般記為N，長度為N的字符串A第一次提到時(shí)一般用A[0..N-1]來表示；
前綴：字符串A[0..N-1]的從A[0]開始的若干個(gè)連續(xù)的字符組成的字符串稱為A的前綴，以下“前綴i”或者“編號為i的前綴”指的都是A[0..i]；
后綴：字符串A[0..N-1]的到A[N-1]終止的若干個(gè)連續(xù)的字符組成的字符串稱為A的后綴，以下“后綴i”或者“編號為i的后綴”指的都是A[i..N-1];

對于一個(gè)長度為N的字符串，將其N個(gè)后綴按字典序大小進(jìn)行排序，得到兩個(gè)數(shù)組sa[i]和rank[i]，sa[i]為排在第i位的后綴的編號（也就是一般說的ord[i]），rank[i]為排在后綴i排在的位置（稱為后綴i的名次）。sa、rank值的范圍均為[0..N-1]。sa和rank互逆，即sa[i]=j等價(jià)于rank[j]=i，或者說成sa[rank[i]]=rank[sa[i]]=i。這里，sa稱為后綴數(shù)組，rank稱為名次數(shù)組。

【2】用倍增算法求后綴數(shù)組：
在論文里，后綴數(shù)組有兩種求法：倍增算法和DC3算法，前者的時(shí)間復(fù)雜度為O(NlogN)，但常數(shù)較小，后者的時(shí)間復(fù)雜度為O(N)，但常數(shù)較大，在實(shí)際應(yīng)用中，兩者的總時(shí)間相差不大，且后者比前者難理解得多（本沙茶理解前者都用了幾天時(shí)間……后者就木敢看了）。這里就總結(jié)一下倍增算法吧囧……
首先，貼一下本沙茶的用倍增算法求后綴數(shù)組的模板： 這里A是待求sa和rank的字符串。

<1>倍增算法的思想：
記R[i][j]為A[i..i+2^j-1]（如果越界，則后面用@填充）在A的所有長度為2^j的子串（越界則后面用@填充）中的名次（rank）值。倍增算法就是按階段求出所有R[i][j]的值，直到2^j>N為止。首先，R[i][0]的就是字符A[i]在A[0..N-1]中的名次，是可以直接用計(jì)數(shù)排序來實(shí)現(xiàn)的。然后，若R[0..N-1][j-1]已知，則可以按照以下方法求出R[0..N-1][j]的值：對每個(gè)i（0<=i<N），構(gòu)造一個(gè)二元組<X_i, Y_i>，其中X_i=R[i][j-1]，Y_i=R[i+2^j][j-1]（若i+2^j>=N，則Y_i=-∞），然后對這N個(gè)二元組按照第一關(guān)鍵字為X，第二關(guān)鍵字為Y（若兩者都相等則判定為相等）進(jìn)行排序（可以用基數(shù)排序來實(shí)現(xiàn)），排序后，<X_i, Y_i>的名次就是的R[i][j]的值。

<2>一開始，對A中的各個(gè)字符進(jìn)行計(jì)數(shù)排序： 這個(gè)木有神馬好說的，在搞懂了基數(shù)排序之后可以秒掉。唯一不同的是這里加了一句：rank[i]=A[i]，這里的rank[i]是初始的i的名次，MS不符合rank[i]的定義和sa與rank間的互逆性。這里就要解釋一下了囧。因?yàn)樵谇髎a的過程中，rank值可能不符合定義，因?yàn)殚L度為2^j的子串可能會(huì)有相等的，此時(shí)它們的rank值也要相等，而sa值由于有下標(biāo)的限制所以不可能有相等的。因此，在過程中，rank其實(shí)是用來代替A的子串的，這樣rank值只需要表示一個(gè)“相對順序”就行了，也就是：rank[i0]>(=, <)rank[i1]，當(dāng)且僅當(dāng)A[i0..i0+2^j-1]>(=, <)A[i1..i1+2^j-1]。這樣，可以直接將A[i]值作為初始的rank[i]值。

<3>j（代替2^j）的值從1開始不斷倍增，對二元組進(jìn)行基數(shù)排序求出新階段的sa值：
注意這個(gè)基數(shù)排序的過程是很特別的。首先，它并不是對A在進(jìn)行排序，而是對上一階段求出的rank在進(jìn)行排序。因?yàn)榍懊嬉呀?jīng)說過，在求sa的過程中，rank就是用來代替A的對應(yīng)長度的子串的，由于不能直接對子串進(jìn)行排序（那樣的話時(shí)間開銷很恐怖的），所以只能對rank進(jìn)行排序。另外，這里在對二元組<x, y>的第二關(guān)鍵字（y）進(jìn)行排序的過程中加了優(yōu)化：這些y其實(shí)就是把上一階段的sa整體左移了j，右邊空出的部分全部用@（空串）填充得到的，由于空串的字典序肯定最小，因此將右邊的空串按照下標(biāo)順序先寫入臨時(shí)sa（代碼中用tmp表示的就是臨時(shí)sa，也就是對第二關(guān)鍵字y排序后的ord結(jié)果），然后，上一階段的sa如果左移后還木有消失的（也就是sa值大于等于j的），再按順序?qū)懭肱R時(shí)sa，就得到了排序結(jié)果。剩下的對x的排序結(jié)果就是上一階段的sa，唯一不同的是對于x相同的，按照臨時(shí)名次遞增的順序。

<4>求出新階段的rank值： 由于下一階段需要使用本階段的rank值，因此在求出了本階段的sa值以后，需要求rank值。（代碼中的tmp起了臨時(shí)rank的作用，目的是節(jié)省空間）
因?yàn)閟a值已經(jīng)求出，因此只要依次掃描sa就可以得到rank值，唯一要做的工作就是找到哪些子串是相等的，它們的rank值應(yīng)該相等，除此之外，rank值只要依次加1即可。判定相等的方法：只需判定rank[i]和rank[i+j]是否都對應(yīng)相等即可。若rank[i+j]越界，用-∞（當(dāng)然任何一個(gè)負(fù)數(shù)都行，代碼中用了-1）來表示。
最后還有一個(gè)優(yōu)化：由于本階段的名次的范圍只有[0..p]這么多，下一階段的“字符集”（其實(shí)就是rank集）的大小SZ可以設(shè)為p+1，這樣可以省一些時(shí)間。

這樣后綴數(shù)組sa和名次數(shù)組rank就全部求完了。

以后還有一些更重要的東東就是AC自動(dòng)機(jī)、后綴數(shù)組等的應(yīng)用問題，算了，以后再搞吧囧。