此文，仅，谈，后缀数组的实现。
应用什么的不存在的。
后缀数组，就是把 1 个字符串的所有后缀排序后的排名数组。
也就是帮字符串的所有后缀排个序。
最后需要求出 1 个 rank 数组，rank[p] 代表，以 p 开头的后缀的排名几何。
这样做有什么用？本文尚且不谈。
怎么去做这个事？
就理解成 n 个字符串排序呗。
怎么快速比较字符串大小？
hash + 2 分/倍增
众所周知，用 hash 做完前缀和后，可以知道字符串子串的 hash 值。
我们可以比较 hash 值比较字符串是否相等，当且仅当 hash 1 样。
所以我们只要 二分/倍增 的找到 2 个字符串，第 1 个不相等的位置，这是有单调性的，然后比较那 1 位的字符就吼啦。
如果边界不好处理，就，把数组弄大 2 倍，空就给 1 个 0 就好了。
这样我们就可以比较字符串大小啦。
把这个写个 cmp ，扔进 sort 里就好。
比较 1 次的时间是 log，sort 也要 log，所以总体时间是 O(nlognlogn)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define ull unsigned long long
using namespace std;
const int ML=2000010;
const int P=131;
ull p[ML],s[ML],c[ML];
int n;
ull geT(int i,int j)
{
if (i==0) return s[j-1];
return s[i+j-1]-s[i-1]*p[j];
}
bool cmP(int p1,int p2) //可以理解为比较 2 个 int 的大小的规则是 int 所示后缀的比较
{
int le,ri;
for (le=0,ri=n+1; le+1<ri; ) //2 分找第 1 个不同的位置
{
int mid=(le+ri)>>1;
if (geT(p1,mid)!=geT(p2,mid)) ri=mid;
else le=mid;
}
if (ri>n) return true;
else return c[p1+ri-1]<c[p2+ri-1];
}
int turN(char ch)
{
if ('0'<=ch && ch<='9') return ch-'0'+1;
if ('a'<=ch && ch<='9') return ch-'a'+1+10;
if ('A'<=ch && ch<='Z') return ch-'A'+1+10+26;
}
char st[ML];
int a[ML];
int main()
{
scanf("%s",st);
n=strlen(st);
for (int i=0; i<n; i++) c[i]=turN(st[i]); //返回值会比 0 大
for (int i=n; i<n+n; i++) c[i]=0; //空是 0 哦
p[0]=1; for (int i=1; i<=n; i++) p[i]=p[i-1]*P; //P 的次幂
s[0]=c[0]; for (int i=1; i<n+n; i++) s[i]=s[i-1]*P+c[i]; //hash 前缀和
for (int i=0; i<n; i++) a[i]=i;
sort(a+0,a+n,cmP);
for (int i=0; i<n; i++) printf("%d ",a[i]+1);
return 0;
}
我们考虑另外 1 种比较字符串大小的方法，这次不是 2 2 比较，而是整体处理了。
假如我们把每个后缀限定 1 个长度 step，只比较 st[p,p+step) 的部分，越界了就给空(0)
这样当 step>=len(st) 的时候，就完成了后缀排序。
所以当我们要求限长为 step 的排序，我们可以从 half=step/2 推得。
我们把我们要比较的 st[p,p+step) 分为 st[p,p+half)+st[p+half,p+step) 2 部分。
然后那太好了，因为我们之前已经算过了限长为 half 的排序，所以我们对于 st[p,p+step) 只要：
以 rank[half][p] 为第 1 关键字，rank[half][p+half] 作为第 2 关键字，来个双关键字排序就好了。
for (int k=1; k<n; k>>=1)
{
for (int i=0; i<n; i++) fi[i]=ra[i],se[i]=ra[i+(1<<k)];
bace_sort(se,n)
bace_sort(fi,n)
updata_rank
}
现在就来学学双关键字排序。
其实这个也不是很高大上，并且，我的理解或许是错的？不然跟个桶排序没有区别啊？望指出。
应为考虑到 rank 的值域只在 [0,len] 所以我们考虑用值域数组(桶)
我们先按第 2 关键字排 1 遍序，再按第 1 关键字再排 1 遍，就可以了？
为什么？只要这个排序是稳定排序就行了，值相同的，会先入为主，而先入是按第二关键字排好序的，所以就保证了双关键字排序。
所以我们考虑做 1 遍排序。
有 1 种比较直观的想法，就是对每个值域建 1 个 vector 就好了。按原序往里面扔进去，再按值域顺序拿出来。当每个点建个栈理解？
bace_sort(key,lim):
for (int i=0; i<=lim; i++) sta[i].clear();
for (int i=0; i<n; i++) sta[key[p[i]].push_back(p[i]);
for (int i=0,tp=0; i<=lim; i++)
for (int j=0,si=sta[i].size(); j<si; j++)
p[tp++]=sta[i][j];
但 vector 慢啊，所以我们可以麻烦 1 点，自己弄个栈呗。
先预处理出每个栈的大小，就可以分配空间，在求出每个栈的起始位置，就可以当个栈用了。
//c:count 表示栈大小，s:strat 表示栈起始位置，a:array 表示映射
bace_sort(key,lim):
for (int i=0; i<n; i++) c[key[p[i]]]++;
for (int i=0,tp=0; i<=lim; c[i++]=0) s[i]=tp,tp+=c[i];
for (int i=0; i<n; i++) a[s[key[p[i]]]++]=p[i];
for (int i=0; i<n; i++) p[i]=a[i];
有了这个东西，就可以 O(n) 双关键字排序。
先做出第 1 次的排序，求出限长为 1 的情况。
然后倍增即可。
还需注意 1 点点的就是排名的更新，相同的，排名 1 样。
还有 1 个优化，当排名已经从 [1,n] 排好时，就可以退了，神速！
/*==================first_step================*/
for (int i=0; i<n; i++) p[i]=i;
bace_sort(st,256)
updata_rank
/*====================up_up===================*/
for (int k=1; k<n; k<<=1)
{
for (int i=0; i<n; i++) fi[i]=ra[i],se[i]=ra[i+k];
bace_sort(se,n)
bace_sort(fi,n)
updata_rank
if (ra[p[n-1]]==n) break; //¼ôÖ¦ÓÅ»¯
}
总代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int ML=1000100;
int ra[ML*2],p[ML],c[ML],s[ML],a[ML],fi[ML],se[ML];
void surffiX_ranK(char *st,int n)
{
#define PD1 (st[p[i]]==st[p[i-1]])
#define PD2 (fi[p[i]]==fi[p[i-1]] && se[p[i]]==se[p[i-1]])
#define updatA_ranK(PD) \
ra[p[0]]=1; \
for (int i=1; i<n; i++) ra[p[i]]=ra[p[i-1]]+!PD;
#define bacE_sorT(keY,lim) \
for (int i=0; i<n; i++) c[keY[p[i]]]++; \
for (int i=0,tp=0; i<=lim; tp+=c[i],c[i++]=0) s[i]=tp; \
for (int i=0; i<n; i++) a[s[keY[p[i]]]++]=p[i]; \
for (int i=0; i<n; i++) p[i]=a[i];
#define pr(a) for (int i=0; i<n; i++) cout<<a[i]<<" "; \
cout<<endl;
/*==================first_step================*/
for (int i=0; i<n; i++) p[i]=i;
bacE_sorT(st,256)
updatA_ranK(PD1)
/*====================up_up===================*/
for (int k=1; k<n; k<<=1)
{
for (int i=0; i<n; i++) fi[i]=ra[i],se[i]=ra[i+k];
bacE_sorT(se,n)
bacE_sorT(fi,n)
updatA_ranK(PD2)
if (ra[p[n-1]]==n) break;
}
for (int i=0; i<n; i++) printf("%d ",p[i]+1);
}
char st[ML];
int main()
{
scanf("%s",st);
surffiX_ranK(st,strlen(st));
return 0;
}
懒癌发作，全是 define，define 超级爽！
讲完啦。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：后缀数组的实现 hash&倍增”