最近感觉自己越来越蒟蒻了……后缀数组不会，费用流不会……

看着别人切一道又一道的题，我真是很无奈啊……

然后，我花了好长时间，终于弄懂了后缀数组。

后缀数组是什么？

后缀$SA$数组

给你一个字符串，让你将每个后缀排序，就是一个后缀数组。

比如，字符串为ababa，就会搞出一个这样的东西：

aabaabababababaSA={4,2,0,3,1};

其中，每个后缀用开始的位置来表示。

$rank$数组

相当于逆着的$SA$，$rank[sa[i]]=i$

#后缀数组怎么求？

方法一：O(N3)O(N^3)O(N3)暴力

打个选择排序，每次比较用$O(N)$的方法。

当然，这样的暴力出不了奇迹。

方法二：O(N2lg⁡N)O(N^2\lg N)O(N2lgN)快排

仅仅是将选择排序变成快排罢了。

##方法三：倍增

倍增1.0

这就是本文的重点了！！！

想想其它的倍增是怎么做的，再想想字符串怎么倍增。

首先，给每个字符赋一个排名，像这样：

'a'->1'b'->2

现在rank={1,2,1,2,1}

然后像下面的这幅图一样搞一搞。

倍增算法的精髓就在这幅图中。

枚举一个$i$，对于每个位置$j$，每次将$j$和j+2ij+2^ij+2i合并到一起（不够补0），然后排名（可以当做是离散化）。

这样就可以求出$rank$，然后求出$SA$。

具体没什么好讲的，只要看懂这幅图，就懂了倍增算法的思想。

这样就可以优化到O(Nlg⁡2N)O(N\lg^2N)O(Nlg2N)了。

倍增2.0

然而，这不是倍增的极限。

可以用基数排序进一步地优化！！！

什么是基数排序，基数排序怎么打，请百度一下（基数排序可以用一维的数组来打，具体看代码实践）。

在此，我有意提醒的是，你可以将数看做一个m进制，在倍增合并两个数时，可以将其看做m进制的两位数，然后对它进行基数排序。

这样就有$O(N\lg N)$的时间复杂度了。

具体见代码。

DC3算法

笔者暂时不会……

---

后缀数组怎么打？

后缀数组其实是比较好理解的，但是，为了追求完美，我们不应光靠自己的理解打模板。

因为自己打的有时会非常丑陋……

看了，理解的网上的标，综合我自己的风格，就打出了个这样的标：

int y[2000003],ws[2000003],wv[2000003];void getSA(char s[],int rank[],int sa[],int n,int m){
    	memset(ws,0,sizeof(int)*m);	memset(y,255,sizeof y);	memset(rank,255,sizeof rank);	for (int i=0;i
    
     =0;--i)		sa[--ws[rank[i]]]=i;	for (int i=1;p
     
      <<=1,m=p)	{
    		p=0;		for (int j=n-i;j
      
       =i)				y[p++]=sa[j]-i;		for (int j=0;j
       
        =0;--j)			sa[--ws[wv[j]]]=y[j];		swap(rank,y);		p=1;		rank[sa[0]]=0;		for (int j=1;j
       
      
     
    

这就是网上通常的打法，当然，风格会有些不一样……

是不是看了后，一头雾水？

别急，慢慢解释。

首先说一下，在这个程序中，$rank$取值是在$[0,n)$范围内的，和上面那张图不一样！

memset(ws,0,sizeof(int)*m);	memset(y,255,sizeof y);	memset(rank,255,sizeof rank);	for (int i=0;i
    
     =0;--i)		sa[--ws[rank[i]]]=i;
    

前面三行赋初值。

这是处理最开始的$rank$和$sa$，也就是还没有合并时。

$ws$数组是一个桶，用于辅助基数排序。

注意第三行rank[i]=s[i]。我们在实践的时候一开始不需要将真正的排名弄出来，我们只需知道它们的相对大小。而sis_isi​作为单个字符，是可以表示它们的相对大小的。

其它就没什么了，要理解好一维的基数排序！

for (int i=1,p=1;p
    
     <<=1,m=p)
    

$i$表示的是对于一个位置$j$，在这一轮中要用$j$和$j+i$合并。

$p$表示不同的字符串的个数，初值设为$1$是为了循环条件$p<n$，显然$1\ge n$时就没必要做了。

为什么循环条件是$p<n$呢？因为我们发现，最后的$rank$数组一定是一个范围在$[0,n)$的排列。

所以$p$顶多为$n$，想想，当$p=n$时，那么其实已经排好序了，没必要再做下去，比如，可以看看上面那张图，可以发现最后一轮是没有必要的。

$m$表示的也是不同字符串的个数，只是因为在下面$p$要被用作计数器罢了。

p=0;		for (int j=n-i;j
    
     =i)				y[p++]=sa[j]-i;
    

当初我看得最久的是这一段……

这其实是一个小优化。

$y$是一个临时的$rank$数组。

在合并后，其实第二关键字可以通过上一次的$sa$数组求出。

先看看二、三行。显然，$[n-i,n)$这段区间内，如果要和后面的合并，只能补$0$，应该说是补$-1$，因为$rank$数组在这个程序中的取值是$[0,n)$。

$-1$一定是最小的，所以先把它们排在前面。

然后看倒数三行，这个就比较难理解了。

对于位置$j$，在这一轮中会对$j-i$有影响，所以说，$j-i\ge 0$

因为$sa$是有序的，所以我们顺序枚举sajsa_jsaj​，将其中满足以上条件的加入$y$中。

for (int j=0;j
    
     =0;--j)			sa[--ws[wv[j]]]=y[j];
    

这一段的作用就是以第一关键字来进行一次基数排序，和上面的那个一样的道理。

swap(rank,y);		p=1;		rank[sa[0]]=0;		for (int j=1;j

$p$起到计数器的作用。

重点是最后一行y[sa[j-1]]==y[sa[j]] && y[sa[j-1]+i]==y[sa[j]+i]

这是在比较saj−1sa_{j-1}saj−1​和sajsa_jsaj​是否相等。如果相等，那么$rank$值应该要一样（不过注意，到最后时$rank$值一定是不同的！）

网上的标这样比较，就不怕爆掉吗？对此，我很不理解，只是开了两倍的数组来解决这个问题。

---

关于LCP

一些概念

$LCP(i,j)$表示$suffix(i)$和$suffix(j)$的公共最长前缀。

$height(i)=LCP(SA[i-1],SA[i])$

很明显，若ranki&lt;rankjrank_i&lt;rank_jranki​<rankj​，则

LCP(i,j)=min⁡k∈(ranki,rankj]heightkLCP(i,j)=\min_{k\in \left(rank_i,rank_j \right]}{height_k}LCP(i,j)=k∈(ranki​,rankj​]min​heightk​

如何求$height$?

首先，我们要知道一个性质：

设hi=heightrankih_i=height_{rank_i}hi​=heightranki​​，也就是$suffix(i)$与它前一名的最长公共前缀。

那么hi≥hi−1−1h_i\geq h_{i-1}-1hi​≥hi−1​−1

证明：

设$suffix(k)$表示$suffix(i-1)$前一名的后缀，hi−1h_{i-1}hi−1​即是它们的最长公共前缀。

当hi−1≤1h_{i-1} \leq 1hi−1​≤1时，显然等式成立。

当hi−1&gt;1h_{i-1} &gt;1hi−1​>1时，可以发现$suffix(k+1)$和$suffix(i)$的公共后缀至少为hi−1−1h_{i-1}-1hi−1​−1。可以画张图理解一下。

所以，综上，hi≥hi−1−1h_i\geq h_{i-1}-1hi​≥hi−1​−1

利用这个性质，我们可以在$O(N)$的时间内求出$height$数组

代码

void getheight(char s[],int rank[],int sa[],int height[]){
    	for (int i=0,k=0;i

其实不必真正地构出个$h$数组。

---

其它

建议数组从$1$开始，或者将$rank$及辅助数组$y$初值设为$-1$，因为在比较时，后面的要补$0$（或$-1$），我就因为这样调了很久……（被罗穗骞大佬的论文坑了）