后缀数组

---

—— 摘要 ——

---

后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能且时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。

---

—— 基本概念 ——

---

在对后缀数组进行定义之前，需要先了解以下几个基础名词：

1. 子串：字符串S的子串 str[i , j] ( i ≤ j )表示从字符串S中提取出S[i],S[i+1],……,S[j]，并将这些单字符依次序连接形成的字符串。
2. 后缀：后缀是指从某个位置i开始到整个字符串末尾结束的一个特殊子串。如果我们将某个字符串的后缀用Suffix(i)来表示，那么Suffix(i)=str[i,strlen(S)]，其中strlen(S)表示字符串S的长度。（在叙述部分，我们假设字符串的索引从1开始，下同）。
3. 字符串大小比较：字符串的大小比较是一种基于字典序进行的比较。比如对于两个字符串a,b，我们可以令i从1开始顺次比较a[i]和b[i]的大小，如果a[i]=b[i]，则令i加1，继续往后比较；否则，一旦出现a[i]<b[i]则认为a<b，反之则认为a>b，结束比较。如果i>strlen(a)或i>strlen(b)都仍未比出结果，则认为字符串长度更短的那个字符串更小。
   从上面字符串的大小比较来看，如果两个字符串的长度不一致，那么将这两个字符串进行比较的结果一定是不等的，因为不满足a=b的必要条件：strlen(a)=stalen(b)。因此对于某个字符串S而言，S的两个不同开头位置的后缀必不相等。
4. 后缀数组：后缀数组sa是一个一维数组，它保存的是1-n的某个全排列，并且保证Suffix(sa[i])<Suffix(sa[i+1])，1≤i≤n。也就是将S的n个后缀从小到大进行排序后，将排好序的后缀的开头位置顺次放进sa中。
5. 名次数组：名次数组rank[i]保存的是Suffix(i)在所有后缀中按从小到大排列的“名次”。

简单说来，后缀数组是“排第几的是谁？”，名次数组是“你排第几？”。容易看出，后缀数组和名次数组为互逆运算。如下图所示：

设字符串的长度为n。为了方便比较大小，可以在字符串的最后面再添加一个字符，要求这个字符没有在前面的字符串中出现过，而且比前面的字符都要小。
任意两个后缀如果直接比较大小，最多需要比较字符n次，也就是说最迟在比较第n个字符时一定能分出“胜负”。而在求出名次数组后，可以仅用0(1)的时间比较出任意两个后缀的大小。但我们的程序在进行求解时并未直接求解rank数组，而是在对后缀数组sa进行求解。实际上，由于后缀数组和rank数组之间存在着互逆性，所以我们在求出后缀数组或名次数组中的其中一个以后，便可以用0(n)的时间求出另外一个。

---

—— 具体实现 ——

---

对于后缀数组的实现，主要有两种算法：

1. 倍增算法
2. DC3算法

DC3算法的代码量稍微有点大，在竞赛中遇到的时候几乎不会用这算法（当然，更多的原因是这玩意儿有点难，我确实是搞不懂），因此下面仅对倍增算法进行介绍。
在对倍增算法进行学习前，要求读者要懂得基数排序的基本思想，否则会很难理解这个算法。如果有不了解这个算法的同学，请先移步这篇博客——基数排序（后缀数组基础）进行学习后再来。
倍增算法的主要思路是：用倍增的方法对每个字符开始的长度为2^k的子字符串进行排序，求出排名，即rank值。k从0开始，每次加1，当2^k大于n以后，每个字符开始的长度为2^k的子字符串便相当于所有的后缀。并且这些子字符串一定都已比较出大小，即rank值中没有相同的值，那么此时的rank值就是最后的结果。每一次排序都利用上次长度为2^k-1的字符串的rank值，那么长度为2^k的字符串就可以用两个长度为2^k-1的字符串的排名作为关键字表示，然后进行基数排序，最后便可得出长度为2^k的字符串的rank值。以字符串“aabaaaab”为例，整个过程如下图所示。其中x、y是表示长度为2^k的字符串的两个关键字。

其具体的解题过程是：
（1）首先计算S[0],S[1],…,S[n-1]的排名(注意这个单个字符的排序)。比如上面，对于aabaaaab，排序后为：1,1,2,1,1,1,1,2；
（2）计算子串S[0,1],S[1,2],S[2,3],…,S[n-2,n-1],S[n-1,null] 的排名（注意最后一个的第二个字符为空），由于我们知道了单个字符的排名， 那么每个子串可以用一个二元组来表示，比如S[0,1]={1,1}，S[1,2]={1,2},S[2,3]={2,1}，等等，也就是aa,ab,ba,aa,aa,aa,ab,bε（ε表示空）的排名，排序后为：1,2,4,1,1,1,2,3
（3）计算子串S[0,1,2,3]，S[1,2,3,4]，S[2,3,4,5]，……，S[n-4,n-3,n-2,n-1]，S[n-3,n-2,n-1]，S[n−2,n−1,]，S[n−1,]的排名，方法与上面相同，也是用一个二元组来表示。
接下来的执行流程和(2)(3)类似：每次使用两个2^x-1长度的子串来计算2^x长度的子串的排名，直到某一次排序后n个数字各不相同，最后就能将rank数组得到。
那在代码中我们怎么通过两个2^x-1长度的子串来计算2^x长度的子串的排名呢？还是基数排序！我们通过基数排序来对具体关键字所在的索引进行排序，这里面有个关键点是：对关键字所在索引进行排序。仔细想，这样的操作最终不就会得到我们的后缀数组么？确实如此。虽然上面图示的流程给你的感觉是在对rank数组进行求解，但实际上rank数组在倍增法中只是作为一个求后缀数组sa的跳板，我们最终的目的是为了得到后缀数组。
纸上谈兵也许会很空洞，下面我们结合具体的代码进行分析：

const int N=15010;
class SuffixArray{
	private:
		static const int MAX=N;
		int wa[MAX],wb[MAX],wd[MAX],r[MAX];
		bool isSame(int *r,int a,int b,int len)
		{ return r[a]==r[b] && r[a+len]==r[b+len]; }
		void da(int n,int m)
		{
			//第一次桶排序，求出字符长度为1时的sa数组 
			int *x=wa,*y=wb,*t;
			for(int i=0;i<m;i++) wd[i]=0;
			for(int i=0;i<n;i++) wd[x[i]=r[i]]++;
			for(int i=1;i<m;i++) wd[i]+=wd[i-1];
			for(int i=n-1;i>=0;i--) sa[--wd[x[i]]]=i;
			for(int j=1,p=1;p<n;j<<1,m=p){
				//对第二关键字排序
				p=0;
				for(int i=n-j;i<n;i++) y[p++]=i;
				for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
				//对第一关键字排序
				for(int i=0;i<m;i++) wd[i]=0;
				for(int i=0;i<n;i++) wd[x[i]]++;
				for(int i=1;i<m;i++) wd[i]+=wd[i-1];
				for(int i=n-1;i>=0;i--) sa[--wd[x[y[i]]]]=y[i];
				//利用指针操作调换两数组的内容 
				t=x,x=y,y=t;
				//更新x数组 
				p=1,x[sa[0]]=0;
				for(int i=1;i<n;i++) x[sa[i]]=isSame(y,sa[i-1],sa[i],j)?p-1:p++;
			}
		}
	public:
		int sa[MAX],n;					//sa表示后缀数组,n表示传递进来的字符串的长度 
		void calSuffixArray(char *s)	//计算后缀数组sa 
		{
			n=0;						//初始化n 
			while(*s){					//遍历字符串 
				r[n++]=*s-'a'+1;		//初始化r数组：将字符型数组转化为数值型数组 
				s++;
			} 
			r[n]=0;						//最后在r数组的末尾再添加一个0 
			da(n+1,27);					//开始求sa数组 
		} 
};

我们以该类中的函数调用顺序来进行说明。
首先是public成员中的calSuffixArray函数，该函数作为其类的唯一入口函数，实际上也就是用于求解后缀数组的唯一方法。该函数接受的参数是一个字符串，这个字符串即是需要被计算后缀数组的目标字符串。在calSuffixArray函数里，首先是通过一个while循环来对字符串s进行遍历，遍历的目的有两个：
① 得到字符串长度，并将其存进变量n中；
② 将字符串的每个字符单独提取出，用相应的数字进行代替，并存进数组r中（比如上面代码的意思是用1-26分别表示字母a-z，当然，本程序的处理对象仅仅是小写字符串，如果含大写字母你可以用*s-‘A’+1来替代，如果含特殊字符(如!、{、%、?、$等)可以用*s-‘A’+1来替代。具体的替代方案需根据你的处理对象并结合ASCII码表得出）。
通过上面的步骤，我们便得到了字符串s的等效替代数组r，这个数组在后面的da函数中才会发挥作用。紧接着，我们就直接调用da函数。这个函数有两个参数：
① n表示你传递的等效替代数组r的长度。由于我们为了方便后面的处理，在数组r的末尾添加了一个0，因此数组r的长度实际上是比字符串s多1的。所以我们在调用da函数时传递进的参数为n+1。
② m指示了你在用基数排序时所用到的“桶”的数量（基数排序是基于桶排序的）。由于我给出的示例是处理仅含小写字母的字符串，而小写英文字母又只有26个，因此在calSuffixArray函数中传递进的参数为27。如果你的处理对象含大小写字母，那么你可以将m改为58；如果你的处理对象含大小写字母和特殊字符，那么你可以将m改为94（具体数值可以根据你的处理对象并结合ASCII码表得出）。

接下来到了最关键的部分：da函数
进入函数首先是进行一个基数排序，代码如下：

for(i=0;i<m;i++) wd[i]=0;
for(i=0;i<n;i++) wd[x[i]=r[i]]++;
for(i=1;i<m;i++) wd[i]+=wd[i-1];
for(i=n-1;i>=0;i--) sa[--wd[x[i]]]=i;

其作用是对长度为1的字符串进行排序，比如对字符串”aabaaaab”进行排序，并将排序后的结果放进后缀数组sa中。而上面的x数组保存的值相当于就算rank值。这里的工作可被视为初始化工作。
接下来是若干次的基数排序，目的是对每个长度为2k的字符串所形成的二元组进行排序。这里的长度是以2的倍数形式递增，所以我们可以用一个循环来实现，然后在每次循环中都对当前长度下的二元组进行排序处理。因此在这部分的排序可分为两次：第一次是对第二关键字排序，第二次是对第一关键字排序。对第二关键字排序的结果实际上可由上一次求得的sa直接算出，没有必要再算一次。代码如下：

for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j) y[p++]=sa[i]-j;

其中变量j表示当前字符串的长度，数组y保存的是对第二关键字排序的结果。然后要对第一关键字进行排序，代码如下：

for(int i=0;i<m;i++) wd[i]=0;
for(int i=0;i<n;i++) wd[x[i]]++;
for(int i=1;i<m;i++) wd[i]+=wd[i-1];
for(int i=n-1;i>=0;i--) sa[--wd[x[y[i]]]]=y[i];

这样便求出了新的sa值。在求出sa后，下一步是更新rank值。这里要注意的是，可能有多个字符串的rank值是相同的，所以必须比较两个字符串是否完全相同，y数组的值已经没有必要保存，为了节省空间，这里用y数组保存rank值。这里又有一个小优化，将x和y定义为指针类型，复制整个数组的操作可以用交换指针的值代替，不必将数组中值一个一个的复制。代码如下：

t=x,x=y,y=t;
p=1,x[sa[0]]=0;
for(int i=1;i<n;i++) x[sa[i]]=isSame(y,sa[i-1],sa[i],j)?p-1:p++;

其中isSame函数的代码是：

bool isSame(int *r,int a,int b,int len)
{ return r[a]==r[b] && r[a+len]==r[b+len]; }

这里可以看到规定r[n-1]=0的好处，如果r[a]=r[b]，说明以r[a]或r[b]，开头的长度为1的字符串肯定不包括字符r[n-1]，所以调用变量r[a+1]和r[b+1]不会导致数组下标越界，这样就不需要做特殊判断。执行完上面的代码后，rank值保存在x数组中，而变量p的结果实际上就是不同的字符串的个数。因此，如果p等于n，那么函数可以结束。因为在当前长度的字符串中，已经没有相同的字符串，接下来的排序不会再改变rank数组，从而也就不会再改变后缀数组sa。
下面给出执行calSuffixArray函数的算法流程图：

下面给出一个求解后缀数组sa的演示程序：

#include<iostream>
using namespace std;

const int N=15010;
class SuffixArray{
	private:
		static const int MAX=N;
		int wa[MAX],wb[MAX],wd[MAX],r[MAX];
		bool isSame(int *r,int a,int b,int len)
		{ return r[a]==r[b] && r[a+len]==r[b+len]; }
		void da(int n,int m)
		{
			//第一次桶排序，求出字符长度为1时的sa数组 
			int *x=wa,*y=wb,*t;
			for(int i=0;i<m;i++) wd[i]=0;
			for(int i=0;i<n;i++) wd[x[i]=r[i]]++;
			for(int i=1;i<m;i++) wd[i]+=wd[i-1];
			for(int i=n-1;i>=0;i--) sa[--wd[x[i]]]=i;
			for(int j=1,p=1;p<n;j<<1,m=p){
				//对第二关键字排序
				p=0;
				for(int i=n-j;i<n;i++) y[p++]=i;
				for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
				//对第一关键字排序
				for(int i=0;i<m;i++) wd[i]=0;
				for(int i=0;i<n;i++) wd[x[i]]++;
				for(int i=1;i<m;i++) wd[i]+=wd[i-1];
				for(int i=n-1;i>=0;i--) sa[--wd[x[y[i]]]]=y[i];
				//利用指针操作调换两数组的内容 
				t=x,x=y,y=t;
				//更新x数组 
				p=1,x[sa[0]]=0;
				for(int i=1;i<n;i++) x[sa[i]]=isSame(y,sa[i-1],sa[i],j)?p-1:p++;
			}
		}
	public:
		int sa[MAX],n;					//sa表示后缀数组,n表示传递进来的字符串的长度 
		void calSuffixArray(char *s)	//计算后缀数组sa 
		{
			n=0;						//初始化n 
			while(*s){					//遍历字符串 
				r[n++]=*s-'a'+1;		//初始化r数组：将字符型数组转化为数值型数组 
				s++;
			} 
			r[n]=0;						//最后在r数组的末尾再添加一个0 
			da(n+1,27);					//开始求sa数组 
		} 
};

int main()
{
	char chs[N];
	cin>>chs;
	SuffixArray suffixArray;
	suffixArray.calSuffixArray(chs);
	for(int i=1;i<=suffixArray.n;i++) cout<<suffixArray.sa[i]+1<<" ";
	cout<<endl; 
	return 0;
}

该程序的作用是对某个仅含小写字母的字符串，求出其对应的后缀数组。比如输入字符串”lljjllj”，效果如下：

数据结构的存在是为了给算法奠基，而算法的意义则是为解决一些实际问题。
下面我们来看一下后缀数组能用于处理些什么问题：

---

—— 应用一：不同子串个数 ——

---

给定一个仅含小写字母的字符串，问其有多少个不同的子串。（如：对于字符串abad而言，其不同子串有：a、b、d、ab、ba、ad、aba、bad、abad共9个）。
如果给的字符串长度在1000以内，我们是可以用暴力枚举的方法来进行求解的，但是长度范围一旦过大，暴力法就不奏效了。此时，我们的后缀数组就派上用场了。
在解释用后缀数组求不同字串数量之前，我们需要先了解一个东西：公共前缀。
什么是公共前缀？比如对于字符串”abcdef”和”abcxyz”而言，其公共前缀显然是子串”abc”；而对于字符串”abcdef”和”uvwxyz”而言，其公共前缀则为空。
我们定义height[i]=suffix(sa[i-1])和suffix(sa[i])的公共前缀长度。即：height数组为排名相邻的两个后缀的公共前缀长度。比如对于字符串”aabaaaab”而言，我们不难得出其height数组的内容如下：

那么对于任意的j和k（rank[j]<rank[k]），suffix(j)和suffix(k)的公共前缀长度为:
min( { height[rank[j]+1],height[rank[j]+2], height[rank[j]+3],…,height[rank[k] } )
比如对于字符串”aabaaaab”而言，其后缀”abaaaab”和”aaab”的公共前缀长度为：
min( { height[3],height[4],height[5],height[6] } ) = min( { 2,3,1,2 } ) = 1

到这里有同学可能有点懵。我们不是来求不同子串个数么？现在咋在整这什么height数组哦。
实际上，对于任何一个子串而言，其都能被表达为某个后缀的前缀。那么求解某个字符串的不同字串个数实际上就等价于求所有后缀之间，不同前缀的个数。如果所有的后缀按照suffix(sa[1])，suffix(sa[2]),suffix(sa[3])，… , suffix(sa[n])的顺序计算，不难发现，对于每一次新加进来的后缀suffix(sa[k]), 它将产生n-sa[k]+1个新的前缀。但是其中有height[k]个是和前面的字符串的前缀是相同的。所以suffix(sa[k])将“贡献”出n-sa[k]+1-height[k]个不同的子串。累加后便是原问题的答案。这个做法的时间复杂度为0(n)。

于是，现在我们的任务是先求出height数组。
如果按height[2]，height[3]， … height [n]的顺序计算，最坏情况下时间复杂度为0(n2)。这样做并没有利用字符串的性质。如果我们定义h[i]=height[rank[i]]，也就是suffix(i)和在它前一名的后缀的公共前缀。那么h数组具有性质：h[i]≥h[i-1]。
此时如果我们按照h[1], h[2], … h[n]的顺序计算，并利用h数组的性质，则时间复杂度可降为0(n)。
在具体实现时，其实没有必要保存h数组，只须按照h[1], h[2], … h[n]的顺序计算即可。代码如下:

void calRank()						//计算名次数组rank 
{  for(int i=1;i<=n;i++) rank[sa[i]]=i;  }
void calHeight()					//计算相邻的两个后缀的最长公共前缀长度数组height 
{
	int j,k=0;
	calRank();
	for(int i=0;i<n;i++){
		if(k) k--;
		int j=sa[rank[i]-1];
		while(r[i+k]==r[j+k]) k++;
		height[rank[i]]=k;
	}
}

这样就可以通过调用calHeight()函数将height数组求出。

在得到了height数组后，我们便可根据前面的分析，直接写出求解某个字符串的不同子串的算法如下：

long long calSubstringNum(char *s)	//对于某个字符串str，计算其不同子串的个数 
{
	calSuffixArray(s);
	calHeight();
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans += n - sa[i] -height[i];
	return ans;
}

下面给出整个过程的完整代码：

#include<iostream>
using namespace std;

const int N=15010;
class SuffixArray{
	private:
		static const int MAX=N;
		int wa[MAX],wb[MAX],wd[MAX],r[MAX];
		bool isSame(int *r,int a,int b,int len)
		{ return r[a]==r[b] && r[a+len]==r[b+len]; }
		void da(int n,int m)						//n表示传递进的字符串的长度，m表示最大桶的数量 
		{
			int *x=wa,*y=wb,*t;
			for(int i=0;i<m;i++) wd[i]=0;
			for(int i=0;i<n;i++) wd[x[i]=r[i]]++;
			for(int i=1;i<m;i++) wd[i]+=wd[i-1];
			for(int i=n-1;i>=0;i--) sa[--wd[x[i]]]=i;
			for(int j=1,p=1;p<n;j<<1,m=p){
				//对第二关键字排序
				p=0;
				for(int i=n-j;i<n;i++) y[p++]=i;
				for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
				//对第一关键字排序
				for(int i=0;i<m;i++) wd[i]=0;
				for(int i=0;i<n;i++) wd[x[i]]++;
				for(int i=1;i<m;i++) wd[i]+=wd[i-1];
				for(int i=n-1;i>=0;i--) sa[--wd[x[y[i]]]]=y[i];
				//利用指针操作调换两数组的内容
				t=x,x=y,y=t;
				//更新x数组 
				p=1,x[sa[0]]=0;
				for(int i=1;i<n;i++) x[sa[i]]=isSame(y,sa[i-1],sa[i],j)?p-1:p++;
			}
		}
	public:
		int sa[MAX],rank[MAX],height[MAX],n;//分别表示后缀数组、名次数组、排名相邻的两个后缀的公共前缀长度数组、传递进来的初始字符串长度 
		void calSuffixArray(char *s)		//计算后缀数组sa 
		{
			n=0;							//初始化n 
			while(*s){						//遍历字符串
				r[n++]=*s-'!'+1;			//初始化r数组：将字符型数组转化为数值型数组
				s++;
			}
			r[n]=0; 						//对于r数组而言，其还需要在最后加一个0方便处理 
			da(n+1,100);					//由于上面多加了个0，因此传递进da函数中的r数组长度需再加1 
		}
		void calRank()						//计算名次数组rank 
		{  
			for(int i=1;i<=n;i++) 
			rank[sa[i]]=i;  
		}
		void calHeight()					//计算相邻的两个后缀的最长公共前缀长度数组height 
		{
			calRank();
			int k=0;
			for(int i=0;i<n;i++){
				if(k) k--;
				int j=sa[rank[i]-1];
				while(r[i+k]==r[j+k]) k++;
				height[rank[i]]=k;
			}
		}
		long long calSubStringNum(char *s)	//对于某个字符串str，计算其不同子串的个数 
		{
			calSuffixArray(s);
			calHeight();
			long long ans=0;
			for(int i=1;i<=n;i++)
				ans += n - sa[i] - height[i];
			return ans;
		}
};

int main()
{
	char chs[N];cin>>chs;
	SuffixArray suffixArray;
	cout<<"字符串："<<chs<<"的不同字串个数为："<<suffixArray.calSubstringNum(chs)<<endl;
	for(int i=1;i<=suffixArray.n;i++) cout<<suffixArray.sa[i]<<" ";		//sa数组的索引从1开始，但是值从0开始 
	cout<<endl;
	for(int i=0;i<suffixArray.n;i++) cout<<suffixArray.rank[i]<<" ";	//rank数组的索引从0开始，但是值从1开始 
	cout<<endl;
	for(int i=1;i<=suffixArray.n;i++) cout<<suffixArray.height[i]<<" ";	//height数组的索引从1开始 
	cout<<endl; 
	return 0;
}

趁热打铁：蓝桥杯 算法提高 着急的WYF（不同子串个数）

---

—— 应用二：最长公共子串 ——

---

我们先来了解下什么是公共子串：如果字符串L同时出现在字符串A和字符串B中，则称字符串L是字符串A和字符串B的公共子串。
现在如果给出两个字符串A和B，让你输出其最长公共子串（Longest Common Substring ,简称LCS）。你要怎么做？
当然，你是可以用暴力法的，但是那样的时间复杂度达到了0(n³)，在字符长度超过1000时就难以胜任了。这时，我们的后缀数组再次出场！

我们知道字符串的任何一个子串都可表达为这个字符串的某个后缀的前缀，因此求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。如果枚举A和B的所有的后缀，那么这样做显然效率低下。由于要计算A的后缀和B的后缀的最长公共前缀，所以可先将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。观察一下，看看能不能从这个新的字符串的后缀数组中找到一些规律。以A=”aaabaa”，B=”abaa”为例，首先我们用一个特殊字符”$”来将这两个字串连接起，得到新的字符串”aaaba$abaa”，然后我们可以得到其height数组的内容如下（其中属于字符串A的后缀用蓝色作为背景、属于字符串B的后缀用黄色作为背景）：

在上表中，容易看出height数组里的最大值为3，并且对于字符串A=”aaabaa”，B=”abaa”而言，其最长公共字串确实是”aba”，长度为3。那是不是所有height值中的最大值就是答案呢？从上表的构建逻辑来看确实是成立的，但是这样的成立建立在一个基础之上：这两个后缀不在同一个字符串中的！所以实际上，只有当suffix(sa[i-1])和suffix(sa[i])不是同一个字符串中的两个后缀时，height[i]才满足要求。而这个条件很容易满足，用一个变量k存放特殊字符”$”所在位置，然后将每次欲更新最大值的那个height[i]所在的后缀用于和k进行一个比较即可。
若记字符串A和字符串B的长度分别为len(A)和len(B)。则求新的字符串的后缀数组和height数组的时间是O(len(A)+ len(B))，然后求排名相邻但原来不在同一个字符串中的两个后缀的height值的最大值，时间也是O(len(A)+ len(B))，所以整个做法的时间复杂度为O(len(A)+ len(B))。时间复杂度已经取到下限，由此看出，这是一个非常优秀的算法。

下面给出“求最长公共子串”的代码：

bool check(int i,int k)							//判断height[i]的两个比较后缀是否不在同一个字符串中（即是否在k的两边）
{
	if( (sa[i-1]-k)*(sa[i]-k)<0 ) return true;	//结果小于0说明异号，异号说明sa[i-1]和sa[i]在k的两边(即要么sa[i-1]<k && sa[i]>k；要么sa[i]<k && sa[i-1]>k) 
	return false;
}

int calLongestCommonSubString(char *a,char *b,char *s)	//计算某两个字符串a,b的最长公共子串s，并返回其长度
{
	int max=0;											//用于保存最长公共子串的长度 
	int pos=strlen(a);									//得到字符串a的长度（之后将用它标记最大height的位置）
	int flagPos=pos;									//记录两个字符中间插入的特殊字符的位置 
	a[pos++]='$';										//在字符串a的末尾插入特殊字符 
	strcpy(a+pos,b);									//将字符串b追加到字符串a的后面
	calSuffixArray(a);									//计算字符串a的后缀数组sa 
	calHeight();										//计算字符串a的rank数组和height数组 
	for(int i=2;i<=n;i++)								//寻找最大的height
		if(height[i]>max && check(i,flagPos)){
			pos=i;										//更新pos 
			max=height[i];								//更新max 
		}
	int x=0,maxPos=max+sa[pos];
	for(int i=sa[pos];i<maxPos;i++)
		s[x++] = a[i];
	return max;
}

最后给出整个过程的完整代码（对于给定的某两个字符串(仅含小写字母)，输出这两个字符串的最长公共子串）：

#include<iostream>
#include<cstring>
using namespace std;

const int N=15010;
class SuffixArray{
	private:
		static const int MAX=15010;
		int wa[MAX],wb[MAX],wd[MAX],r[MAX];
		bool isSame(int *r,int a,int b,int len)
		{ return r[a]==r[b] && r[a+len]==r[b+len]; }
		bool check(int i,int k)
		{
			if( (sa[i-1]-k)*(sa[i]-k)<0 ) return true;	//结果小于0说明异号，异号说明sa[i-1]和sa[i]在k的两边 
			return false;
		} 
		void da(int n,int m)
		{
			int *x=wa,*y=wb,*t;
			for(int i=0;i<m;i++) wd[i]=0;
			for(int i=0;i<n;i++) wd[x[i]=r[i]]++;
			for(int i=1;i<m;i++) wd[i]+=wd[i-1];
			for(int i=n-1;i>=0;i--) sa[--wd[x[i]]]=i;
			for(int j=1,p=1;p<n;j<<2,m=p){
				p=0;
				for(int i=n-j;i<n;i++) y[p++]=i;
				for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
				for(int i=0;i<m;i++) wd[i]=0;
				for(int i=0;i<n;i++) wd[x[i]]++;
				for(int i=1;i<m;i++) wd[i]+=wd[i-1];
				for(int i=n-1;i>=0;i--) sa[--wd[x[y[i]]]]=y[i];
				t=x,x=y,y=t;
				p=1,x[sa[0]]=0;
				for(int i=1;i<n;i++) x[sa[i]]=isSame(y,sa[i-1],sa[i],j)?p-1:p++;
			}
		}
	public:
		int sa[MAX],rank[MAX],height[MAX],n;
		void calSuffixArray(char *s)
		{
			n=0;
			while(*s){
				r[n++]=*s-'a'+1;
				s++;
			}
			r[n]=0;
			da(n+1,100);
		}
		void calRank()
		{
			for(int i=1;i<=n;i++)
				rank[sa[i]]=i;
		}
		void calHeight()
		{
			calRank();
			int k=0;
			for(int i=0;i<n;i++){
				if(k) k--;
				int j=sa[rank[i]-1];
				while(r[i+k]==r[j+k]) k++;
				height[rank[i]]=k;
			}
		}
		long long calSubStringNum(char *s)
		{
			calSuffixArray(s);
			calHeight();
			long long ans=0;
			for(int i=1;i<=n;i++)
				ans += n-sa[i]-height[i];
			return ans;
		}
		int calLongestCommonSubString(char *a,char *b,char *s)	//计算某两个字符串a,b的最长公共子串s，并返回其长度 
		{
			int max=0;											//用于保存最长公共子串的长度 
			int pos=strlen(a);									//得到字符串a的长度（之后将用它标记最大height的位置）
			int flagPos=pos;									//记录两个字符中间插入的特殊字符的位置 
			a[pos++]='$';										//在字符串a的末尾插入特殊字符 
			strcpy(a+pos,b);									//将字符串b追加到字符串a的后面
			calSuffixArray(a);									//计算字符串a的后缀数组sa 
			calHeight();										//计算字符串a的rank数组和height数组 
			for(int i=2;i<=n;i++)								//寻找最大的height
				if(height[i]>max && check(i,flagPos)){
					pos=i;										//更新pos 
					max=height[i];								//更新max 
				}
			int x=0,maxPos=max+sa[pos];
			for(int i=sa[pos];i<maxPos;i++)
				s[x++] = a[i];
			return max;
		}
};

int main()
{
	char chs[N],chs_[N],ans[N];
	cin>>chs>>chs_;
	SuffixArray suffixArray;
	cout<<suffixArray.calLongestCommonSubString(chs,chs_,ans)<<endl;
	cout<<ans<<endl;
	return 0;
}

本文参考自：
《国家集训队论文》罗穗骞
《后缀数组：倍增法和DC3的简单理解》Only the Strong Survive 的博客
感谢他们在文章中精彩的推论和分析，使我能在巨人的肩膀上学习。

---

---

目录

概念介绍

后缀

后缀树

后缀数组

简单应用：查找子串

求后缀数组：倍增法

sa和rk数组

算法流程

sort模板（详细注释版）

基排序法

最长公共前缀（Longest Common Prefix）   height数组

例题

---

概念介绍

这一部分特别鸣谢党哥的精彩讲解

• 后缀

后缀数组可以解决大部分的字符串问题，如查找子串，最长重复子串，最长公共子串等。

后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=S[i…len(S)-1]。比如 abcdefg 的suffix(5)就是fg。

• 后缀树

例S=“vamamadn”

（因树的建立比较麻烦，用数组替代）

• 后缀数组

后缀数组(SA[i]存放排名第i大的后缀首字符下标)

后缀数组 SA 是一个一维数组，它保存1..n 的某个排列SA[1] ，SA[2] ，…,SA[n] ，并且保证Suffix(SA[i])<Suffix(SA[i+1])， 1<=i<n 。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。例S=“vamamadn”

简单应用：查找子串

求后缀数组：倍增法

sa和rk数组

名次数组（rank[i]存放suffix(i)的优先级） 名次数组 Rank[i] 保存的是 Suffix(i) 在所有后缀中从小到大排列的“名次”

sa是suffix array后缀数组 记录后缀 rk是rank array 记录名次 
rk记录的是第i个子串排第几，也就是说
rk的下标i的含义是后缀子串的起始位置，rk[i]存放的是后缀排序结果
这个后缀子串的起始位置指的是后缀首字母在string的第几位，比如bcda的后缀bcda排第0位(下标从0开始计算),d排第2位 所以其定义域是[0,s.size()-1]
排序结果:a排第0,bcda排第1,cda排第2,da排第3 更多参考见下
sa记录的是排第i的是谁，也就是说
sa的下标i的含义是后缀字典序排序结果，sa[i]存放的是后缀子串的起始位置 
这个排序结果是从小到大按字典序排序，例如sa[0]代表的后缀可能以a打头 但是sa[0]不一定是0 因为字符串第一位不一定是a 比如bcda sa[0]代表的后缀是a,而sa[0]=3 
若sa[j]=0，说明sa[j]代表的后缀是整个字符串，j的值根据字典序排序判断 例如bcda,bcda在4个后缀中排第二，则sa[1]=0        
sa[i]<sa[i+1] 最后sa[]存放的是0~n-1的全排列 
二者互为逆运算，因此sa[rk[i]]=i(i表示后缀起始位置)、rk[sa[i]]=i(i表示后缀排序结果) 

算法流程

第一步的数值是字符-'a'得到的hash映射值，很明显有重复值，因此我们要降重

第二步是以2为长度单位，前后两两合并，这么做是因为字符串比较本身就是从前向后逐位比较，因此hash比较很合适，正常情况下位数不够补充的是-1而不是0（因为0本身就是a的映射）

第三部长度单位*2，继续比较，循环到无重

然后排序，rk赋值为排名，这里是从小到大升序排序

然后通过sa和rk的转化关系sa[rk[i]]=i(i表示后缀起始位置)求sa

所以图9.6的i是起始位置

上述算法很容易爆int或long long数据范围（hash的缺点）

因此我们简化算法

每次hash后根据排名进行重排序

然后hash

循环往复

反正rk记录的都是排名，表达方式不同，但数学意义相同，因此算法正确性显然可证

循环至无重复为止

实际上在代码实现的时候能继续优化，具体方式我们看下面的代码

sort模板（详细注释版）

sort排序本身时间复杂度O(nlogn)，外层k的for循环是logn，所以整体时间复杂度

每个函数甚至大部分行的代码我都详细注释了，这些注释是我认真推敲每行代码得来的，如果谬误敬请指出。

注释尽矣，更复何言？

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500010;
int sa[maxn],rk[maxn],tmp[maxn];//sa与rk见下 tmp是过渡数组
string s;
int n,k;
/*sa是suffix array后缀数组 记录后缀 rk是rank array 记录名次
rk记录的是第i个子串排第几，也就是说
rk的下标i的含义是后缀子串的起始位置，rk[i]存放的是后缀排序结果
这个后缀子串的起始位置指的是后缀首字母在string的第几位，比如bcda的后缀bcda排第0位(下标从0开始计算),d排第2位 所以其定义域是[0,s.size()-1]
排序结果:a排第0,bcda排第1,cda排第2,da排第3 更多参考在第20行
sa记录的是排第i的是谁，也就是说
sa的下标i的含义是后缀字典序排序结果，sa[i]存放的是后缀子串的起始位置
这个排序结果是从小到大按字典序排序，例如sa[0]代表的后缀可能以a打头 但是sa[0]不一定是0 因为字符串第一位不一定是a 比如bcda sa[0]代表的后缀是a,而sa[0]=3
若sa[j]=0，说明sa[j]代表的后缀是整个字符串，j的值根据字典序排序判断 例如bcda,bcda在4个后缀中排第二，则sa[1]=0
sa[i]<sa[i+1] 最后sa[]存放的是0~n-1的全排列
二者互为逆运算，因此sa[rk[i]]=i(i表示后缀起始位置)、rk[sa[i]]=i(i表示后缀排序结果)*/

bool cmp(int i,int j) { //sort的比较函数 靠前的参数是数组中靠前的元素 传入的参数就是数组存放的元素 而sa数组存放的就是后缀起始位置 所以i和j代表的是后缀起始位置
	if(rk[i]!=rk[j]) { // 在上一轮排序或者初始化时已经比较出大小 就不用继续比了
		return rk[i]<rk[j];//排序是根据数组值排下标 根据sa下标的定义，后缀字典序排名小的sa[]下标靠前，因此以后缀字典序排名从小到大排sa
	} else { //排名相同，降重
		int ri,rj;
		ri=i+k<n?rk[i+k]:-1;//i和j代表子串起始位置 i+k>=n说明长度已经超了，没有这么长的位置了  如果前几位全部相同，长度小的小 直接赋值为最小值
		rj=j+k<n?rk[j+k]:-1;//能到这里说面前几位相同，那么直接比较i+k位即可 即使rk[i+k]不存在 正常情况下他也要比存在的情况小，所以比较结果仍正确
		return ri<rj;
	}
}

void calc() {
	for(int i=0; i<n; i++) {
		rk[i]=s[i];//rk： 第i个子串排第几 由于字符本身有大小 因此可以先初始化为字符本身的大小
		sa[i]=i;//sa:排第i的是谁  同上，暂时初始化为自己
	}
	for(k=1; k<n; k*=2) { //k是长度 倍增排序 PPT第六页的第二张图
		sort(sa,sa+n,cmp);
		tmp[sa[0]]=0;//过渡数组
		/*判断前一个字典序的后缀首字符和这个字典序的后缀首字符在排序上是否相同
		根据sa定义,sa[i]<sa[i+1],即以i为首的后缀排名<j的,rk[i]<rk[j],如果cmp返回0,说明rk[i]>=rk[i+1],即以i为首的后缀排名>=j的
		那就说明sa[i]和sa[i+1]在本轮没有被排序所分开，也就是rk[i]==rk[i+1],那么二者过渡数组值相同
		如果cmp返回1，说明sa[i]和sa[i+1]在本轮排序已经被分开了,那么二者过渡数组值差1*/
		for(int i=0; i<n-1; i++) {
			tmp[sa[i+1]]=tmp[sa[i]]+cmp(sa[i],sa[i+1]);//过渡数组记录的实际上就是排名，如果二者rk相同，那么排名肯定相同 否则的话排名差1
		}											   //这一步的基础是之前已经用sort进行过初步排序，使得rk不严格单调 循环是为了让他严格单调
		for(int i=0; i<n; i++) {
			rk[i]=tmp[i];//重赋值rk，赋值后更接近真实排名，方便cmp降重(降重靠的就是不同的后缀长度不同，以此降重)
		}
	}
}

int find(string s,string t,int *sa) { //在s中查找子串t;sa是s的后缀数组 返回值是子串最后一次出现的位置 
	int i=0,j=s.size();
	while(j-i>1) {
		int k=(i+j)>>1;				//二分法，操作O(logn)次
		if(s.compare(sa[k],t.length(),t)<0)	//匹配一次，复杂度是O（m）
			i=k;
		else j=k;
	}
	if(s.compare(sa[j],t.size(),t)==0)	//找到了，返回t在s中的位置
		return sa[j];
	if(s.compare(sa[i],t.size(),t)==0)
		return sa[i];
	return -1;				//没找到
}
int main() {
	while(cin>>s) {
		n=s.size();
		calc();
/*		for(int i=0; i<n; i++) {//输出后缀数组 
			cout<<"以第"<<i<<"位为首的后缀"<<s[i]<<"的字典序排名为"<<sa[i]<<"\n";
		}
		cout<<"\n";*/
		string t;//查找子串  返回值是子串最后一次出现的位置 
		cin>>t;
		cout<<find(s,t,sa)<<endl;
	}
}

基排序法

以下内容特别鸣谢大佬们的精彩讲解

https://blog.csdn.net/qq845579063/article/details/51447772基排序详解

https://www.cnblogs.com/zwfymqz/p/8413523.html#_label4后缀数组详解

排序时间复杂度,r是基数，m是排序的数的位数，很小，基本是常数，外层循环是logn，近似为knlogn,k=

详细注释版模板，每个数组每句代码每个重难点均有详注

#include<iostream>//https://www.cnblogs.com/zwfymqz/p/8413523.html#_label4
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
const int maxn=1e6+50;
using namespace std;
char s[maxn];
int y[maxn],x[maxn],cnt[maxn],sa[maxn],rk[maxn],height[maxn],wt[30];
int n,m;
inv putout(int x) {//快写 
	if(!x) {
		putchar(48);
		return;
	}
	rint l=0;
	while(x) wt[++l]=x%10,x/=10;
	while(l) putchar(wt[l--]+48);
}
inv get_SA(char s[],int n,int m) {//s[i]下标从1开始 到n结束 长度为n m为字符集个数,即桶的个数 最后一行会输出sa数组，不需要请注释掉 
	/*假设已经得到了w长度的排名，要更新2w长度的排名
	sa[i]：长度为w的后缀中，排名为i的后缀的位置 			下标是整个后缀的排名 数值是位置 位置指的是后缀首字符 三个位置同义，指向统一，因此可以嵌套 
	x[i]：长度为w的后缀中，从第i个位置开始的后缀的排名 		下标是位置 数值是(第一关键字)排名 相当于rank  有sa[x[i]]==i x[sa[i]]==i 
	y[i]：长度为2w的后缀中，第二关键字排名为i的后缀的位置 	下标是第二关键字排名 数值是位置 
	cnt[x[i]]	cnt是基排序的桶	这里的语义比较容易让人迷惑，桶为什么要存储排名呢？事实上，x[]的排名和大小是对应的
	桶要把字符存进去，就是把字符的大小存进去，也是把字符的排名存进去，在前几次排序中，相同大小->相同排名->相同的桶	*/
	for (rint i=1; i<=m; i++) cnt[i]=0;//初始化cnt桶
	for (rint i=1; i<=n; i++) ++cnt[x[i]=s[i]];//cnt数组是桶 
	for (rint i=2; i<=m; i++) cnt[i]+=cnt[i-1];//做cnt的前缀和，我们就可以得出每个关键字最多是在第几名
	for (rint i=n; i>=1; i--) sa[cnt[x[i]]--]=i;//将所有桶中记录依次收集到sa中  cnt可以起到去重的作用，根据sa[x[i]]==i用i来初始化sa 
	for (rint k=1; k<=n; k<<=1) {//上面四句是第一关键字基排序，下面两句是排序第二关键字，不需要用到基排序 
		rint num=0;
		for (rint i=n-k+1; i<=n; i++) y[++num]=i;//第n-k+1到第n位是没有第二关键字的（即空串） 所以排名在最前面 
		for (rint i=1; i<=n; ++i) if (sa[i]>k) y[++num]=sa[i]-k;//后缀排名为i的首字符位置 在后缀数组中是否在第k位以后
		//如果满足(sa[i]>k) 那么它可以作为别人的第二关键字，就把以它作为第二关键字的第一关键字的位置sa[i]-k添加进y就行了
		//sa[i]-k是因为sa[i]存储的是后缀排名为i的位置，第一关键字的位置是第二关键字的位置前移k位 而下标i是排名，排名靠前的先加入y 
		//所以i枚举的是第二关键字的排名，第二关键字靠前的先入队
		for (rint i=1; i<=m; i++) cnt[i]=0;//初始化cnt桶 下面四句是第一关键字基排序 
		for (rint i=1; i<=n; i++) cnt[x[i]]++;//因为上一次循环已经算出了这次的第一关键字 所以直接加就行了
		for (rint i=2; i<=m; i++) cnt[i]+=cnt[i-1]; //前缀和 第一关键字排名为1~i的数有多少个
		for (rint i=n; i>=1; i--) sa[cnt[x[y[i]]]--]=y[i],y[i]=0;//重难点 请回顾23~25行三个数组下标和数值的数学意义 
		//我按排名从大到小枚举第二关键字，得到的t=y[i]是后缀首字母位置，再用x[t]定位到首字母的第一关键字的排名 
		//那么cnt[x[y[i]]]就表示当第一关键字相同时，第二关键字较大的这个后缀的排名是啥 第一关键字不同时，cnt[q]的值域就不一样，自然能分出大小 
		//得到了排名，就可以访问桶，我们也就能更新sa了 赋值号右边是y[i]，遵循sa[x[i]]==i的恒等式 同时清零y，为下一步做准备 
		swap(x,y);//这里不用想太多，因为要生成新的x时要用到旧的，就把旧的复制下来，没别的意思 之后x数组就变成y数组，也就是y数组承担rk数组的作用 
		x[sa[1]]=1;
		num=1;
		for (rint 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;//和sort一样，重排序rk数组，使得rk数组更集中，降低时空复杂度 
			//因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字 这里当两个后缀上一轮排名相同时本轮也相同
		if (num==n) break;//num==n说明排名不同的已经到达了n，也就是全部后缀排名均不相同，成功去重，退出循环，降低时间复杂度 
		m=num;//这里就不用那个122了，因为都有新的编号了,可以优化降低时空复杂度（主要是时间复杂度） 
	}
	for (rint i=1; i<=n; ++i) putout(sa[i]),putchar(' ');//输出sa数组 不需要请注释掉 
}
inv get_height() {
	rint k=0;
	for (rint i=1; i<=n; ++i) rk[sa[i]]=i;
	for (rint i=1; i<=n; ++i) {
		if (rk[i]==1) continue;//第一名height为0
		if (k) --k;//h[i]>=h[i-1]-1;
		rint j=sa[rk[i]-1];
		while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
		height[rk[i]]=k;//h[i]=height[rk[i]];
	}
	putchar(10);
	for (rint i=1; i<=n; ++i) putout(height[i]),putchar(' ');
}
int main() {
	gets(s+1);
	n=strlen(s+1);
	m=122;
//因为这个题不读入n和m所以要自己设
//n表示原字符串长度，m表示字符个数，ascll('z')=122
//我们第一次读入字符直接不用转化，按原来的ascll码来就可以了
//因为转化数字和大小写字母还得分类讨论，怪麻烦的
	get_SA(s,n,m);
//get_height();
}

纯享版

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
const int maxn=1e6+50;
using namespace std;
char s[maxn];
int y[maxn],x[maxn],cnt[maxn],sa[maxn],rk[maxn],height[maxn],wt[30];
int n,m;
inv putout(int x) {//快写 
	if(!x) {
		putchar(48);
		return;
	}
	rint l=0;
	while(x) wt[++l]=x%10,x/=10;
	while(l) putchar(wt[l--]+48);
}
inv get_SA(char s[],int n,int m) {//s[i]下标从1开始 到n结束 长度为n m为字符集个数,即桶的个数 最后一行会输出sa数组，不需要请注释掉 
	for (rint i=1; i<=m; i++) cnt[i]=0;//初始化cnt桶
	for (rint i=1; i<=n; i++) ++cnt[x[i]=s[i]];//cnt数组是桶 
	for (rint i=2; i<=m; i++) cnt[i]+=cnt[i-1];//做cnt的前缀和，我们就可以得出每个关键字最多是在第几名
	for (rint i=n; i>=1; i--) sa[cnt[x[i]]--]=i;//将所有桶中记录依次收集到sa中  cnt可以起到去重的作用，根据sa[x[i]]==i用i来初始化sa 
	for (rint k=1; k<=n; k<<=1) {//上面四句是第一关键字基排序，下面两句是排序第二关键字，不需要用到基排序 
		rint num=0;
		for (rint i=n-k+1; i<=n; i++) y[++num]=i;//第n-k+1到第n位是没有第二关键字的（即空串） 所以排名在最前面 
		for (rint i=1; i<=n; ++i) if (sa[i]>k) y[++num]=sa[i]-k;//后缀排名为i的首字符位置 在后缀数组中是否在第k位以后
		for (rint i=1; i<=m; i++) cnt[i]=0;//初始化cnt桶 下面四句是第一关键字基排序 
		for (rint i=1; i<=n; i++) cnt[x[i]]++;//因为上一次循环已经算出了这次的第一关键字 所以直接加就行了
		for (rint i=2; i<=m; i++) cnt[i]+=cnt[i-1]; //前缀和 第一关键字排名为1~i的数有多少个
		for (rint i=n; i>=1; i--) sa[cnt[x[y[i]]]--]=y[i],y[i]=0;//重难点 请回顾23~25行三个数组下标和数值的数学意义 
		swap(x,y);//这里不用想太多，因为要生成新的x时要用到旧的，就把旧的复制下来，没别的意思 之后x数组就变成y数组，也就是y数组承担rk数组的作用 
		x[sa[1]]=1;
		num=1;
		for (rint 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;//和sort一样，重排序rk数组，使得rk数组更集中，降低时空复杂度 
			//因为sa[i]已经排好序了，所以可以按排名枚举，生成下一次的第一关键字 这里当两个后缀上一轮排名相同时本轮也相同
		if (num==n) break;//num==n说明排名不同的已经到达了n，也就是全部后缀排名均不相同，成功去重，退出循环，降低时间复杂度 
		m=num;//这里就不用那个122了，因为都有新的编号了,可以优化降低时空复杂度（主要是时间复杂度） 
	}
	for (rint i=1; i<=n; ++i) putout(sa[i]),putchar(' ');//输出sa数组 不需要请注释掉 
}
inv get_height() {
	rint k=0;
	for (rint i=1; i<=n; ++i) rk[sa[i]]=i;
	for (rint i=1; i<=n; ++i) {
		if (rk[i]==1) continue;//第一名height为0
		if (k) --k;//h[i]>=h[i-1]-1;
		rint j=sa[rk[i]-1];
		while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
		height[rk[i]]=k;//h[i]=height[rk[i]];
	}
	putchar(10);
	for (rint i=1; i<=n; ++i) putout(height[i]),putchar(' ');
}
int main() {
	gets(s+1);
	n=strlen(s+1);
	m=122;
	get_SA(s,n,m);
//get_height();
}

最长公共前缀（Longest Common Prefix）   height数组

以下内容特别鸣谢大佬的精彩讲解

https://www.cnblogs.com/lykkk/p/10520070.html 

https://www.cnblogs.com/victorique/p/8480093.html#autoid-1-2-2

height数组才是后缀数组的精髓

先说定义

i号后缀：从i开始的后缀

lcp(x,y)：字符串x与字符串y的最长公共前缀，在这里指x号后缀与y号后缀的最长公共前缀（原数组）

height[i]：lcp(sa[i],sa[i−1])，即排名为i的后缀与排名为i−1的后缀的最长公共前缀（字典序）

H[i]：height[rank[i]]，即i号后缀与它前一名的后缀的最长公共前缀(原数组)

性质：H[i]⩾H[i−1]−1

证明：

 这里有一点要注意的就是，最后一行的至少是如何解释

我们知道，k+1和i不一定是排名上的相邻关系，也就是说rk[i]-1!=k+1也是很可能的

因此我们必须明白一个性质：排名差距越远，相似度越低

什么意思？排名1号和2号的后缀相似度一定不小于1号和3号，如下图所示

sa[1]和sa[3]的相似度低于sa[1]和sa[2]，这是很显然的一个性质，但是在枯燥的逻辑推理中却很容易被忽略

A对C的相似度比B对C的相似度低，就意味着A和C的lcp不大于B和C的lcp

那么，如果rk[i]-1!=k+1，rk[i]-1的相似度一定低于k+1，那么rk[i]-1和rk[i]的lcp不大于rk[i]和k+1的lcp

因此，H[i]>=H[i-1]-1，大于等于号证明完毕

如果rk[i]-1==k+1，大于等于号变为等于号

定理理解起来很不容易，但是求起来那是相当的轻松啊

注意下面代码求的是height[i]，即字典序排序后相邻lcp关系

利用了h[i]=height[rk[i]]，height[i]=h[sa[i]];

inv get_height() {
	rint k=0;
	for (rint i=1; i<=n; ++i) rk[sa[i]]=i;//sa已经求出来了，初始化rk 
	for (rint i=1; i<=n; ++i) {
		if (rk[i]==1) continue;//第一名height为0
		if (k) --k;//h[i]>=h[i-1]-1;
		rint j=sa[rk[i]-1];
		while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;
		height[rk[i]]=k;//h[i]=height[rk[i]];
	}
//	putchar(10);
//	for (rint i=1; i<=n; ++i) putout(height[i]),putchar(' ');
}

so easy 

注意:

定义LCP（大写）是排名后i,j的最长公共前缀

下面为height的参考图

例题

https://www.luogu.com.cn/problem/P4248

可供参考的题解包括但不限于

https://www.luogu.com.cn/blog/asuldb/solution-p4248

https://www.luogu.com.cn/blog/leozhang/solution-p4248

https://www.cnblogs.com/heyujun/p/10305797.html

下面简单分析一下

 这一部分等于

推导：以样例的5个字母为例，我们计算的区间如下，n=5

1,2 1,3 1,4 1,5

      2,3 2,4 2,5

            3,4 3,5

                  4,5

统计每个数字出现次数，发现均为4次，也就是n-1，每个数字i贡献均为n-i+1,等差数列求和即可

右半部分：

如果我们遍历到k的时候求得左端点为l，右端点为r，那么区间长度就是(k-l+1)*(r-k+1)

也就是两个闭区间长度积

Why?

以[2,5]为例，k=3

2        3        4

                    5

我们以k分割左右，然后开始从每一个数连线

从2开始连线，2-3,2-4,2-5，可以发现左边的每个数能连r-k+1个区间，一共是(k-l)(r-k+1)个区间

k能连接k自己，形成区间[k,k]，形成1个区间

k右边每个数都能与k相连，形成r-k个区间

累加得(k-l)(r-k+1)+(r-k+1)=(k-l+1)(r-k+1)

还有最后一个数学问题：如何处理重复最小值？

比如3 1 1 1 3

如果我们左右端点都取不严格单调，也就是左闭右闭，那么计算到第二个数部分区间为2-3 2-4

但是计算到第三个数时又有3-2出现（也就是2-3）显然区间会重复

如果左右都严格单调，左开右开，显然区间会很少，漏取了

所以我们开一头闭一头，一端严格一端不严格，做到重复最小值只取一次就可以了。至于闭哪端，whatever

数学分析到此结束，剩下的就是代码问题了，第一部分不需要技术含量，第二部分套模板再来个单调栈计算l,r，然后算个数，这没问题吧？

那么，代码略