后缀数组真心是强有力的字符串处理工具，有兴趣的可以参考下其他资料，比如集训队论文什么的。
我这里只是总结下我这两天学习的。
顾名思义，后缀数组，就是字符串后缀组成的数组。
比如abcde
就有后缀
abcde
bcde
cde
de
e
将这些后缀按字典序排序后组成的数组就叫后缀数组
设SA是后缀数组，对于bace的后缀
bace
ace
ce
e
按字典序排序未ace,bace,ce,e
那么SA[1]=ace,SA[2]=bace...
当然也不用记录一个字符串，用这个后缀在原组数的位置就可以表示这个后缀了
SA[1]=2,SA[2]=1...
然后还有个Rank数组，和SA正好相反
Rank[i]表示i后缀的排名
比如Rank[ace]=1,即Rand[2]=1
其实Rank就是SA的逆，Rank[SA[i]]=i
废话这么多，我们有这么一个数组有啥好处呢？
当然是为了利用这个数组的特性来做一些处理啦。
----------分割线-----------
既然SA这么有用，该怎么球呢，现在有两种方法
倍增，DC3
前者nlogn的复杂度，后者n的复杂度
具体怎么做，可以查阅其他资料（逃
-----------继续分割----------
后缀数组可以做很多神奇的事情。。。
比如呢，一个字符串，求最长重复字串（字串可重叠）
要是不会后缀数组，我一看，就会晕掉= =，尼玛好麻烦，要枚举每个字串的节奏么。
先引入一个概念height数组
height[i]=lcp(SA[i-1],SA[i]),lcp表示最长公共前缀
设h[i] = height[rank[i]]，h数组有个很好用的性质
h[i] >= h[i-1] -1
这样我们就能用O(n)的时间求出height数组了
来证明下
首先是显而易见的
lcp(A_SA[x] , A_SA[z]) = min_x<y<=z{lcp(A_SA[y-1] , A_SA[y])}
简单的说就是rank x到z之间的lcp是之间每个相邻的lcp的最小值，这个不用说也知道是对的嘛
那我们就得到
Fact 1. lcp(A_SA[y-1] , A_SA[y]) >= lcp(A_SA[x] , A_SA[z]) x<y<=z
就是说在排名x,z字符串之间的字符串的lcp都大于等于lcp(x,z)，这很显然
Fact 2. 如果lcp(A_SA[x-1] , A_SA[x]) > 1 那么 Rank[SA[x-1]+1] < Rank[SA[x]+1]
也是很明显的结论，因为这两个字符串有公共前缀，那么这个相同的前缀并不影响他们排名，即取消这个字符rank也是不变的
Fact 3. 如果lcp(A_SA[x-1] , A_SA[x]) > 1 那么lcp(A_SA[x-1]+1 , A_SA[x]+1) = lcp(A_SA[x-1] , A_SA[x]) - 1
继续使用显然这个词，这两个x-1,x有公共前缀，那么向后移动一位的字符串的lcp当然只他们没有移动时候-1啦
下面给出一个lemma
先定义
p=rank[i-1],q=rank[i]
j-1=SA[p-1],k=SA[q-1]
lemma 如果lcp(A_j-1,A_i-1) > 1 那么 lcp(A_k,A_i)>=lcp(A_j,A_i)
证明：
lcp(A_j-1,A_i-1)>1 => rank[j] < rank[i] ，by Fact 2
先把i,j,p,q,k什么的属性解释清楚吧
p,q是rank，p是i位置后缀的rank，q是i-1位置的后缀的rank
j-1是排在p前一位的后缀位置，k是排在q前一位的后缀位置
Fact2是说有两个后缀存在公共前缀，那么去掉一个字符后他们的rank也不变的
rank[j-1] = rank[sa[p-1]] = p-1
rank[i-1] = p
所以本身rank[j-1] < rank[i-1]所以 rank[j] < rank[i]
rank[k]=rank[SA[q-1]] =q-1=rank[i]-1
所以rank[j] <= rank[k] = rank[i]-1
所以 lcp(A_k,A_i)>=lcp(A_j,A_i)，这就很明显了k,i在j,i之间，所以他们的lcp要大于等于j,i
ok，现在我们来证明
如果 height[p] = lcp(A_j-1,A_i-1) > 1 那么 height[q] = lcp(A_k,A_i) >= height[p] -1
lcp(A_k,A_i) >= lcp(A_j,A_i) = lcp(A_j-1,A_i-1) - 1
-----证明结束--------
其实写了那么多证明，感觉一点都不直观，我还是习惯直观一点的
那么设后缀k是i-1前面那么一个，那么h[i-1]就是lcp(k,i-1)啦
如果lcp(k,i-1)<=1，那么就是很显然的 h[i]>=h[i-1]-1了（因为-1是0了。。囧
若lcp(k,i-1)>1，那么呢我们可以得到lcp(k+1,i) = h[i-1]-1
显然rank[k] < rank[i-1]那么rank[k+1] < rank[i]
显然k排在i-1前面，然后他们有公共前缀，去掉公共的前缀k+1还是排在i前面的
rank[k+1] ....rank[i]-1...rank[i] , lcp(i,k+1) <= lcp(rank[i]-1,i)
所以嘛h[i] >= h[i-1]-1 , 由Fact1得到
附球height的伪代码
for i = 1 to n rank[sa[i]] = i h = 0 for i = 1 to n if rank[i] > 1 j = sa[rank[i]-1] while a[i+h] == a[j+h] h = h + 1 height[rank[i]] = h if h > 0 h = h - 1