后缀数组的定义

——《高级数据结构》
1.区间
闭区间[i,j]={i,…,j}，开区间[i,j)=[i…j-1]
2.字符串
待构建后缀数组的字符串用T来表示。T的长度为n,下标范围为0到n-1。字符串中第i个字符用ti表示，所以T[0,n)=t0t1…tn-1。在C语言中，字符串数组末尾以特殊字符‘\0’结尾（即T[n]=‘0’),为了方便我们用 $代表结束符，并且它的字典序最小。我们可以扩展这一点，即对于 j > = n, 有 t i =$ 。
3。后缀
对于i属于[0,n)，后缀i为从T中第i个字符开始直到末尾的子串，即T[i,n)。我们把T[i,n)记为Suffix(i)。
4。前缀
字符串T的长度为len的前缀记为T的len次方。特别情况：如果len超过T的长度，那么该前缀即为T本身。
5。后缀集合
对于集合C属于[0,n)，后缀集合Suffix（C）={Suffix(i)|i属于C}。
6。字符串序关系比较
这里使用“字典序比较”的方法。对于长度分别为n和m的字符串U和V，它们的大小比较方式如下：
（1）令i=0;
(2) 如果i>=m并且i<n，那么U<V，终止；；否则，如果 i>=n并且i<m，那么U>V,终止；否则，如果i>=m并且n=m，那么U=V，终止；否则，转（3）；
（3）如果U[i]=V[i],令i增加1，转（2）；否则，如果U[i]>V[i],那么U>V，终止；否则，如果U[i]<V[i],终止。
根据以上比较过程不难发现，任意两个后缀都不可能具有相同的字典序，因为字典序相同的必要条件的长度相等在这里不能满足。
7。后缀数组
后缀树组SA的构建过程即对后缀集合Suffix[0,n)进行排序的过程。SA是一个0道到n-1的排列，满足Suffix(SA[0])<Suffix(SA[1])<…<Suffix(SA[n-1]).
8。名次数组
名次数组Rank可以看做后缀树组SA的反函数，即如果有SA[i]=k,那么Rank[k]=i。简而言之，SA数组回答的是第几个字符开始，而Rank数组回答的是第k个字符开始的后缀排名是多少
二：
后缀数组的构建
1。一种直接的构建算法
基于后缀树组的定义，我们可以得到一种简单的构造算法。应用于比较的排序算法，我们可以再O(nlog2n)次后缀比较得到的结果。但是后缀比较不同于一般的整数比较，由上一节对于字典序的定义可知，比较两个字符串的序关系需要O（n）的时间复杂度，其中n为字符串的长度。因此，这种简单的排序算法的时间复杂度为O(n的2次方log2n）.
2倍增算法
虽然上面介绍的排序算法不太可能直接应用，但是通过该算法我们可以发现冗余——因为后缀排序不同于一般的字符串按照字典序排序，前者有着更紧的约束。通过对排序过程的优化，我们可以将后缀树组构建的时间复杂度优化到O（nlog2n）。在开始算法介绍之前，我们队记号做一些约定。
子串T1的k次方：T1的k次方=T[i,min{i+k,n}]。也就是说，T1的k次方就是从T中的第i个字符开始的长度为k的子串（或者因为长度超过范围而被截断；或者说，如果Suffix(i)的长度不小于k，那么T1的k次方是后缀Suffix(i)的长度为k的前缀，否则就是Suffix(i)本身。为了方便，我们用T[0,n)的k次方表示子串Ti的k次方的集合：T[0.n)={Ti的k次方，i属于[0,n)}
k-阶段名次数组Rankk:即对于T[0,n)的k次方这n个子串进行排序后的名次数组。类似地，我们还可以定义k-阶段后缀树组SAk。
倍增算法描述：
倍增算法（Prefix Doubling）从计算Ranki和SAi开始，一直计算到Rank2的d次方和SA2的d次方，其中2的d次方>=n。以下我们采用一种类似于数学归纳法的方式描述算法框架。
（1）。计算Ranki和SAi.这一步等价于对T[0,n)的1次方这n个子串进行排序，即对字符串T的n个字符进行排序。由于单个字符的排序，使用一般的快速排序即可。更快速的方式是利用桶排序或者基数排序，可以再O(n）的时间复杂度内完成该步骤。
（2）。如果Rankp和SAp已经计算好了（其中p为2的整数次幂），现在来考察如何计算Rank2p和SA2p。当前阶段是对T[0,n)的2p进行排序，为了进行两两之间的比较，对于两个子串Ti的2p次方和Tj的2p次方。
1Ti的2p次方<Tj的2p次方等价于Ti的p次方<Tj的p次方或（Ti的p次方=Tj的p次方且Ti+p的p次方<Tj+p的p次方）；
2 Ti的2p次方=Tj的2p次方等价于Ti的p次方=Tj的p次方且Ti+p的p次方=Tj+p的p次方。
注意：上面子串Ti+p的p次方或者Tj+p的p次方的下标可能会超过范围。但是对于j>=n，有tj=$，因此若下标范围超接界，那么肯定在Ti的p次方和Tj的p次方的关系中已经比较出结果了，因此不用担心这个问题。
所以，T[0,n)的2p次方的排序可以看做二元组（Ti的 p次方，Tj的p次方）。由于已经计算出了Rankp,所以对于任意的Ti的p次方和Tj的p次方，其大小关系就是Rankp[i]和Rankp[j]的大小关系。这里的排序可以使用快速排序，当然使用基数排序可以得到更加好的效果。
（3）最后计算Rank2的d次方和SA2的d次方，这便是最后所需要的两个数组Rank和SA。我们来分析一下倍增算法的时间复杂度：由于每次排序的子串长度都是上一次的两倍，因此这种排序执行的次数为O(log2n)；如果使用基数排序，则时间复杂度仍为O（nlog2n）。
倍增算法代码：
#include
#include
//输入依次为待处理的字符串（离散化从1到 upperBound的整数）指针，处理结果SA(后缀数组)指针，名次数组指针，字符串长度以及字符范围*/
using namespace std;

void doubling(int* st,int* SA,int* rank,int n,int upperBound)
{
/以下这两个计数数组是桶排序时用到的，因为基数排序对象的位数只有两位（即二元组），所以可以转化为两次桶排序/
int* cnt=new int[upperBound+3],cntRank=new int[n+3];
//以下名次数组分别为第一阶段和第一阶段名次数组以及二元组两个元素各自排名
int rank1=new int[n+3],rank2=new int[n+3];
//临时后缀数组
int tmpSA=new int[n+3];
memset(cnt,0,sizeof(cnt)*(upperBound+3));
for(int i=0;i<n;i++)
cnt[st[i]]++;
for (int i=1;i<=upperBound;i++)
cnt[i]+=cnt[i-1];

	//首先获得第一阶段的名次，即对单个字符进行排序
for (int i=0;i<n;i++)
 rank[i]=cnt[st[i]]-1;
 
 for (int l=1;l<n;l*=2)
 {
 	//根据上一阶段的结果构造当前阶段的二元组来进行基数排序
	 for (int i=0;i<n;i++)
	   {
	     rank1[i]=rank[i];
		 if (i+1<n)
		    rank2[i]=rank[i];
		 else rank2[i]=0; 
	   }
	   //以下为基数排序过程 
     memset(cntRank,0,sizeof(cntRank)*(n+3)); 
     for (int i=0;i<n;i++)
        cntRank[rank2[i]]++; 
	 for (int i=0;i<n;i++)
	    cntRank[i]+=cntRank[i-1];
	 for (int i=n-1;i>=0;i--)
	 {
	 	tmpSA[cntRank[rank2[i]]-1]=i;
	 	cntRank[rank[i]]--;
	 }
	 memset(cntRank,0,sizeof(int)*(n+3));
	 for (int i=0;i<n;i++)
	   cntRank[rank1[i]]++;
	  
	 for (int i=1;i<n;i++)
	   cntRank[i]+=cntRank[i-1];
	 
	 for (int i=n-1;i>=0;i--)
	 {
	 	SA[cntRank[rank1[tmpSA[i]]]-1]=tmpSA[i];
		cntRank[rank1[tmpSA[i]]]--; 
	  }
	  //以上代码将基数排序过程分解为两次桶排序
	  //根据当前得到的后缀树组计算名次数组，以得到下次排序时所需要的名次
	  //信息
	  
	  rank[SA[0]]=0;
	  for (int i=1;i<n;i++)
	   {
	  	rank[SA[i]]=rank[SA[i-1]];
	  	if (!((rank1[SA[i]]==rank1[SA[i-1]])&&(rank2[SA]==rank2[SA[i-1]])))
	       rank[SA[i]]++; 
	   } 
 } 
delete[] cnt;delete[] cntRank;delete[] rank1;delete rank2[];delete[] tmpSA;

}

由后缀树得到后缀数组
在本章的前半部分，我们介绍了由ukkonen算法提出的后缀树的线性时间构造算法。当然，还有许多人侧重于不同方面提出了不同的后缀树线性时间构造算法。M.Farach在1997年
提出了一种能够应对大型字符集的构造算法,而这种算法衍生中后缀数组的线性时间构造算法。该算法的大致流程如下：
1.构建从奇数位置开始的后缀的后缀树，这种递归做法将问题规模缩减为原来的一半。
2.用第1步的结果构造剩下来的后缀的后缀树。
3.将上述两个后缀树合并为一个。
其中，第3步是本章法最为复杂的一步。如果从这种算法得到的后缀树中得到后缀数组，虽然能够在理论线性时间构造出后缀数组，但是由于本身已经进行了后缀树的构造，因此在构建过程
中空间和时间上相比后缀树没有任何优势。本身不对该算法进行更深入的介绍。但是，这种分而治之的思想很有启发性，一下将要介绍的后缀树组构建算法正是基于该思想。