后缀数组（Suffix Array）是一个字符串的所有后缀按词典顺序排列。 此文档中数组的索引从0开始。 s[j.Len[s]-1]称为后缀j。 sa[i]=j表示原字符串的所有后缀按词典顺序排列，第I个是后缀j。 字符串的后缀数组是唯一的。
sa根据等级调查后缀号码，与之对应的是rank数组，根据后缀号码调查等级。 sa[i]=j=rank[j]=i。
对后缀进行排序有什么用呢？ 字符串的所有子串都可以表示为后缀的前缀。 对于有序的序列，我们两分钟就能找出来。 设文本列的长度为n，模板列的长度为m。 直接二分可实现o(nLGn )-o (m-lgn )的时间复杂度。 用height序列优化可以得到o(nLGn ) O(m lg n )。 height是后缀数组中两个相邻后缀的最长公共前缀。
后缀数组的结构可以用o(nLGn )的时间生成字符串的后缀数组——加倍算法，从前面的段落可以看出。 似乎存在O(N )的算法，在OI中很少使用。
有很多对数量进行排序的方法。 在基于比较的排序中，可以最快地进行o(nLGn )，理论上无法进一步优化。 在我们的模型中，数之间的比较是o(1)，而字符串的比较是o ) n )。 所以，我们需要另辟蹊径。
除了基于比较的排序外，还有计数排序、基数排序等。 字符串集合太大，无法对计数进行排序。 但是，字符集往往很小，所以应该尝试基于计数排序的基数排序。 如果每次使用O(N )进行计数排序，进行n个循环的计数排序，则全部为o ) N^2)，仍然是不理想的。
词典有什么特性？ 如果将s和t都分解为[0.i]、[i 1.len-1]，则s t=(s[0.i] t[0.i] )或s[0.i]=t[0.i]，且s [ i1 . 一是可以递归或递归比较两个字符串二、这类似于与二元组的比较！
如果将sa_k作为只取每个后缀的前缀k得到的“后缀数组”，则rank_k类似。 我们可以根据它们计算出sa_2k和rank_2k。 该图标如下所示：
将二元组(rank_k[i]，rank_k[i k] )作为后缀I的关键字进行排序，得到sa_2k。 rank_k的等效项有助于快速比较两个后缀。 从sa_2k中计算出rank_2k。 i k越界了怎么办？ 我采用的方法是把那个rank定为-1。 然后，您会发现放置rank[n]=-1就可以了。
使用快速排序，至此，我们得到了用o(nLG^2n )构建后缀数组的算法。
储存区的取值范围为0~n-1。 统计一下各存储体可以允许对应多少个后缀吧。 可以按照之前前提的基数排序吗？ 基数从低到高循环，每次都以该位数为关键词采用某种稳定的排序算法，如计数排序，最后得到有序序列。 以上banana的例子中，以k=4时的二元组为例：
Pretty cool！
一种简单的实现方法是，以rank_k[i k]为关键词，对所有后缀进行排序，得到pre。 并且，将rank_k[i]作为关键字，对pre计数进行排序，得到sa_2k。
有可以优化的地方吗？
什么是sa_k？ 将rank_k[i]作为关键字对所有后缀进行排序的结果。 现在，我们把rank_k[i k]作为关键词。 对于满足i k n的后缀，其优先级保持不变，但对于i k=n的后缀，根据上述约定，第二个关键字必须等于-1，并且必须位于pre的开头。 所以，我们可以直接从sa_k中得到pre。
开始写代码吧。 以下代码只是为了说明，为了便于记述而打乱了顺序。
# include cstring # includealgorithmvoidbuild _ sa (chars [ ]，int n ) { memset(b ) b，0，sizeof ) int } * sigma _ size for(intI=0； i n； I ) b(s ) I )-) a )； for(intI=1； i SIGMA_SIZE； I ) B(I )=B(I-1 )； for(intI=n-1； i=0； -I ) sa(-b ) s ) I )-'a ) )=I； int m=rank[sa[0]]=0； for(intI=1； i n； I ) rank[sa[i]]=m =s[sa[i]]！=s[sa[i-1]]； m； 这一段求sa_1和rank_1。 假设SIGMA_SIZE MAX_N。 字符集较大时，std:sort即可，不影响渐近的执行时间。 m是不同的rank种数。
int *pre=t； for(intk=1； m n； k *=2，m}{for(intI=0，p=k； i n； I )
if (sa[i] >= k) pre[p++] = sa[i]-k; for (int i = 0; i < k; ++i) pre[i] = n-k+i;这一段求出pre。t是一个指针，定义为全局变量。
int b[MAX_N], buff[2][MAX_N+1], *t = buff[0];接下来根据第一关键字计数排序。
memset(b, 0, sizeof(int)*m); for (int i = 0; i < n; ++i) ++b[rank[i]]; for (int i = 1; i < m; ++i) b[i] += b[i-1]; for (int i = n-1; i >= 0; --i) sa[--b[rank[pre[i]]]] = pre[i];至此，已求出新的sa。接着，我们来计算rank。
m = r[sa[0]] = 0; for (int i = 1; i < n; ++i) r[sa[i]] = m += rank[sa[i]] != rank[sa[i-1]] || rank[sa[i]+k] != rank[sa[i-1]+k]; swap(r, rank); }r是一个中间“数组”。这时pre数组已经没用了，所以它们可以共用一块内存。rank也定义为指针。
int *&pre = t, *&r = t;现在可以看到定义数组指针的用意。无须copy，无须memcpy，swap即可。DP里搞滚动数组也可以借鉴这个技巧。
int b[MAX_N], sa[MAX_N], buff[2][MAX_N+1], *t = buff[0], *rank = buff[1];别忘了在for k外面加上这句！
rank[n] = r[n] = -1;两个后缀i、j，设i < j。若j+k <= n，则rank[i+k]和rank[j+k]有定义。若j+k > n，则必有rank[j] < rank[i]，根据短路法则，无须再比较rank[i+k]和rank[j+k]。
最后，还有：
} 最长公共前缀设后缀sa[i]和sa[j]的最长公共前缀为LCP(i, j)，有定理：LCP(i, j) = min{height[k] | min{i, j} < k <= max{i, j}}。
一开始，强健的冷风告诉我这很显然，我是拒绝的。然而现在我也想建议大家使用显然法……
还是证一下吧。先证一个引理，设i < k <= j，则LCP(i, j) = min{LCP(i, k), LCP(k, j)}。当k = j时显然成立。以下说明k < j时的情形。
设LCP(i, k)=a，LCP(j, k)=b，LCP(i, j)=c，sa[i]=x，sa[j]=y，sa[k]=z，不妨设a <= b。那么，s[x..x+a-1] = s[z..z+a-1]，s[z..z+b-1] = s[y..y+b-1]，由传递性，s[x..x+a-1] = s[y+a-1..y+a-1]，故LCP(i, j) >= a。由字典序的定义，后缀数组中i~k项后缀的前c个字符相等，故a >= LCP(i, j)。证毕。
结合这个引理和数学归纳法，上述定理成立。
所以说height数组很重要啦。有了它，再求求RMQ，任意两后缀的最长公共前缀就搞定了。
上面这个定理有个推论，帮我们线性时间求height：height[rank[i]] >= height[rank[i-1]]-1。后缀i和i-1，拿掉i-1的第一个字符，二者就相等了。考虑sa[rank[i-1]-1]=p-1，则后缀p-1<后缀i-1。如果它俩的第一个字符相等，那么，有后缀p < 后缀i，由定理，有height[rank[i-1]]-1 = LCP(sa[p], sa[i]) <= height[rank[i]]。如果它俩的第一个字符不等，则height[rank[i-1]] = 0，显然成立。推论得证。
height[rank[i]]相对于前一项只能增加或减1，最多累计减少(n-1)个1，且height[rank[i]] <= n。于是，按照height[rank[0]], height[rank[1]], height[rank[2]], …的顺序愉快地递推吧！
UOJ #35是一道模板题，我的代码：http://uoj.ac/submission/93286。
写在最后后缀数组最初是从兄弟学校的MYJ学长那里学的。研究了一下强健的冷风老师的代码，然后默写了一遍……UOJ #35始终是0分，CodeVS的模板题过了。那时我还没发现UOJ可以看一部分数据啊……我自己也不太清楚自己在写什么，这就是照着别人代码打的坏处。但是自己写不出来啊。于是这个数据结构和莫队算法等等在今年1~4月于匆忙中囫囵吞枣的知识一样，属于不可用的。
这次是自己重新写的，但心底里对于以前的代码还是有个模糊的印象。根据强健的冷风老师的代码修改的。有两个地方比我更优：一是他通过共用pre和r（原代码变量名不一样），只用4n的空间；二是引入m变量。
本文参考了强健的冷风、tdjb编著的《算法竞赛入门经典训练指南》和国家集训队2004年badlt前辈的《后缀数组》一文。
如有不当之处，欢迎指正～