后缀数组
后缀数组
后缀数组是处理字符串问题的有力工具。
一.写在前面的话
告别严谨枯燥的数学证明，
告别头绪繁多的“算法类比”
告别大佬神仙的各种专业术语，
举例让你感性理解。
笔者将浅略地讨论倍增法求解后缀数组。如果你不知道倍增，也不知道后缀数组，那么恭喜，你来对了！
二.计数排序
不要忽视这部分，我当年就卡在这儿
针对如下问题：
给定：n个数的关键字key，和一个长度为n的指针数组ord
保证：所有关键字key均小于等于1百万，ord是n的一个排列
要求对ord进行稳定的排序，使得任取i，有
key[ord[i]]≤key[ord[i+1]]
“稳定”的含义是：当上式取等时，ord和ord[i+1]的相对位置不变
输出排序后的数组sa
样例输入：
| key0 | key1 | key2 | key3 | key4 | key5 | key6 | key7 |
|---|---|---|---|---|---|---|---|
| 97 | 97 | 98 | 97 | 97 | 97 | 97 | 98 |
{ 7 0 2 3 4 5 1 6 }= ord
样例输出：
{ 0 3 4 5 1 6 7 2 }=sa
表示
最小的是key0,然后是key3，紧接着是key4....为什么跳过key1呢？因为在ord中0、3、4都比1出现的早。
说白了，就是给定一个指针数组和每个指针所指向的关键字，要求对这些指针进行稳定的排序。
| 排序前 ord | 7(98) | 0(97) | 2(98) | 3(97) | 4(97) | 5(97) | 1(97) | 6(97) |
|---|---|---|---|---|---|---|---|---|
| 排序后 sa | 0(97) | 3(97) | 4(97) | 5(97) | 1(97) | 6(97) | 7(98) | 2(98) |
如果关键字小于等于1百万，那么
我们可以用计数排序在O(1百万)的时间内解决。步骤如下：
- 第一步
- 各种初始化
- 第二步
- 我们计算出每个关键字出现的次数,记作f。
样例中,f[97]=6,f[98]=2。值得注意的是，f在将来要排好序的sa数组上，还有着"区间长度"的意义。
| 排序后 sa | 0(97) | 3(97) | 4(97) | 5(97) | 1(97) | 6(97) | 7(98) | 2(98) |
|---|---|---|---|---|---|---|---|---|
| * | * | * | * | * | * | + | + |
: 上图中星号区间长度为f[97],加号区间长度为f[98]
- 第三步
-
计算f的前缀和，用前缀和更新f，
样例中f[97]=6,f[98]=8
那么f在sa中的意义就变为指针，准确地说，是
指针数组的队尾指针
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6=f[97] | 7 | 8=f[98] |
|---|---|---|---|---|---|---|---|---|---|
| 排序后 sa | 0(97) | 3(97) | 4(97) | 5(97) | 1(97) | 6(97) | 7(98) | 2(98) | 空 |
| 97的空队尾(亦98的实队头) | 98的空队尾 |
- 第四步
-
这一步最复杂，我们要逆序扫描原指针数组ord,把所有ord放入sa中。
样例中，我们已知
| 排序前 ord | 7(98) | 0(97) | 2(98) | 3(97) | 4(97) | 5(97) | 1(97) | 6(97) |
|---|
: 那我们依次把6(97)、1(97)、5(97)。。。放进sa中
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6=f[97] | 7 | 8=f[98] |
|---|---|---|---|---|---|---|---|---|---|
| 排序后 sa | 未知 | 未知 | 未知 | 未知 | 未知 | 未知 | 未知 | 未知 | 空 |
| 位置 | 0 | 1 | 2 | 3 | 4 | 5=f[97] | 6 | 7 | 8=f[98] |
|---|---|---|---|---|---|---|---|---|---|
| 排序后 sa | 未知 | 未知 | 未知 | 未知 | 未知 | 6（97） | 未知 | 未知 | 空 |
| 位置 | 0 | 1 | 2 | 3 | 4=f[97] | 5 | 6 | 7 | 8=f[98] |
|---|---|---|---|---|---|---|---|---|---|
| 排序后 sa | 未知 | 未知 | 未知 | 未知 | 1(97) | 6（97） | 未知 | 未知 | 空 |
| 位置 | 0 | 1 | 2 | 3=f[97] | 4 | 5 | 6 | 7 | 8=f[98] |
|---|---|---|---|---|---|---|---|---|---|
| 排序后 sa | 未知 | 未知 | 未知 | 5(97) | 1(97) | 6（97） | 未知 | 未知 | 空 |
: 最后就得到了答案
- 代码实现:
- 简直一步行代码，刚刚好4行
void SORT()
{
for(i=0;i<=m;i++) f[i]=0;
for(i=0;i<n;i++) f[key[ord[i]]]++;
for(i=0;i<=m;i++) f[i]+=f[i-1];
for(i=n-1;i>=0;i--)
sa[--f[key[ord[i]]]]=ord[i];
}
总结一下
给定一个指针数组ord和每个指针所指向的关键字key，要求对这些指针进行稳定的排序，输出排序后的数组sa。
如果最大关键字不超过1百万，通过计数排序就可以在O(1百万)的时间内完成排序
以下我将简称这个过程为
以key为关键字对ord进行计数排序
三、双关键字的计数排序
大佬们也喜欢称它为基(ji)数(lao)排序。事实上，基数排序是多关键字的计数排序，应用肯定比双关键字广泛。不够对于后缀数组来说，卖个关子，你仅需知道双关键字就够了
针对如下问题
给定n个数对(key1[0],key2[0])(key1[1],key2[1])...(key1[n-1],key2[n-1])
保证所有关键字小于等于1百万
要求对n个数对双关键字排序(其实也可以不稳定)，然后
输出一个数组sa，sa[i]表示第i大的数对在原“数对数组”的位置（即对指针排序)
样例输入：
| 位置0 | 位置1 | 位置2 | 位置3 | 位置4 | 位置5 | 位置6 | 位置7 |
|---|---|---|---|---|---|---|---|
| 0(97,97) | 1(97,98) | 2(98,97) | 3(97,97) | 4(97,97) | 5(97,97) | 6(97,98) | 7(98,0) |
样例输出：
| 0(97,97) | 3(97,97) | 4(97,97) | 5(97,97) | 1(97,98) | 6(97,98) | 7(98,0) | 2(98,97) |
|---|
解法就是，令指针数组sa[i]=i,然后以key2位关键字对sa计数排序，接着以key1为关键字对sa再计数排序，最后输出sa即可。不多说，放代码：
void SORT()
{
for(i=0;i<=m;i++) f[i]=0;
for(i=0;i<n;i++) f[key[ord[i]]]++;
for(i=0;i<=m;i++) f[i]+=f[i-1];
for(i=n-1;i>=0;i--)
sa[--f[key[ord[i]]]]=ord[i];
}
int main()
{
cin>>key1>>key2;//皮一下
for(i=0;i<n;i++)
key[i]=key2[i],
ord[i]=i;
SORT();
for(i=0;i<n;i++)
key[i]=key1[i],
ord[i]=sa[i];
SORT();
cout<<sa;//再皮一下
}
四、后缀排序
我们将走进字符串的世界，准备好了吗？
如表，s="aabaaaab"有8个后缀，（显然有36个非空子串)
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 字符串s | a | a | b | a | a | a | a | b |
| 后缀0 | a | a | b | a | a | a | a | b |
| 后缀1 | a | b | a | a | a | a | b | |
| 后缀2 | b | a | a | a | a | b | ||
| 后缀3 | a | a | a | a | b | |||
| 后缀4 | a | a | a | b | ||||
| 后缀5 | a | a | b | |||||
| 后缀6 | a | b | ||||||
| 后缀7 | b |
我们说“后缀i”实际上是在说“以s[i]为首的后缀”。换言之，i，是一个指针，指向一个后缀（字符串）。考虑这么一个问题：
给定一个字符串s,长度为n,
要求你将0,1,2..n-1，这n个指针以“后缀i”为关键字排序，
然后输出排序后的指针数组sa
PS.两个后缀是依据字典序比较大小的，由于任意两个后缀长度不等，所有任意两个后缀不可能相等。故输出唯一
样例输入:
aabaaaab
样例输出:
3 4 5 0 6 1 7 2
样例解释:
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 字符串s | a | a | b | a | a | a | a | b |
| 后缀3 | a | a | a | a | b | |||
|---|---|---|---|---|---|---|---|---|
| 后缀4 | a | a | a | b | ||||
| 后缀5 | a | a | b | |||||
| 后缀0 | a | a | b | a | a | a | a | b |
| 后缀6 | a | b | ||||||
| 后缀1 | a | b | a | a | a | a | b | |
| 后缀7 | b | |||||||
| 后缀2 | b | a | a | a | a | b |
这里只给一个nlgn的倍增法。实际上还有O(n)的DC3算法，O(n)的SA-IS算法,还有O(nlg^2)的哈希。不再赘述
后缀排序最重要的是一个数组rk[]，代表估价(或是排名rank),其余的内容均是计数排序
现在，我们考虑n个长为2的子串，为了方便，我们在最后一个子串上补0
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|---|
| 字符串s | a | a | b | a | a | a | a | b | |
| 子串0 | a | a | |||||||
| 子串1 | a | b | |||||||
| 子串2 | b | a | |||||||
| 子串3 | a | a | |||||||
| 子串4 | a | a | |||||||
| 子串5 | a | a | |||||||
| 子串6 | a | b | |||||||
| 子串7 | b | 0 |
把它们排序，实际上是个双关键字的计数排序。排完序后，我们可以把排名看作这个子串的“估价”。发现问题的可分解性。具体地：
规定长度为1的子串的估价为其ascll码，那么
长度为2的子串i的估价，可以看作一个二元组(前半段的估价,后半段的估价)在所有长度为2的n个子串中的排名。
同理
长度为4的子串i的估价，可以看作一个二元组(前半段的估价,后半段的估价)在所有长度为4的n个子串中的排名。
不断地倍增，会得到所有后缀的估价(排名)
我下面放两个代码，第一个可读性好，但是常数大；第二个把常数优化了一下（实际上只是换个头文件，去掉子函数罢了）。
//这份代码可读性好，但是常数大
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+2;
int f[maxn];//作为临时数组
int key[maxn],ord[maxn],sa[maxn];//计数排序?
int rk[maxn],tp[maxn];//rk和tp本质上是一样的，tp是rk的倍增
char s[maxn];//输入的串
int n,i,j,m;
bool dif(int i,int j){return rk[i]!=rk[j]||tp[i]!=tp[j];}//两个个二元数对中，只要有一组关键字不同，两个数对就是不同
void SORT()//计数排序
{
for(i=0;i<=m;i++) f[i]=0;
for(i=0;i<n;i++) f[key[ord[i]]]++;
for(i=0;i<=m;i++) f[i]+=f[i-1];
for(i=n-1;i>=0;i--)
sa[--f[key[ord[i]]]]=ord[i];
}
void get_sa()
{
int i,k;
for(i=0;i<n;i++) rk[i]=s[i];
for(k=1;k<n;k<<=1)
{
for(i=0;i<n;i++)
tp[i]=(i+k<n)?rk[i+k]:0;
for(i=0;i<n;i++)
key[i]=tp[i],
ord[i]=i;
SORT();
for(i=0;i<n;i++)
key[i]=rk[i],
ord[i]=sa[i];
SORT();
f[sa[0]]=1;//注意必须是1而不是0。0是用来补的
for(i=1;i<n;i++)
f[sa[i]]=f[sa[i-1]]+dif(sa[i],sa[i-1]);
for(i=0;i<n;i++)
rk[i]=f[i];
m=n;//这一行不能省，尤其n比m大的时候
}
}
int main()
{
scanf("%s",&s);
n=strlen(s);
m=128;//字符集大小
get_sa();
for(i=0;i<n;i++)
printf("%d ",sa[i]);
return 0;
}
//这份代码常数小一点
#include<cstdio>
#include<cstring>
#include<algorithm>//这个头文件比bits快多了
using namespace std;
const int maxn=1e6+2;
int f[maxn];
int key[maxn],ord[maxn],sa[maxn];
int rk[maxn],tp[maxn];
char s[maxn];
int n,i,j,m;
//这边不再设子函数
void get_sa()
{
int i,k;
for(i=0;i<n;i++) rk[i]=s[i];
for(k=1;k<n;k<<=1)
{
for(i=0;i<n;i++)
tp[i]=(i+k<n)?rk[i+k]:0;
//for(i=0;i<n;i++)printf("(%d,%d)\n",rk[i],tp[i]);
memset(f,0,sizeof(f));
for(i=0;i<n;i++) f[tp[i]]++;
for(i=0;i<=m;i++) f[i]+=f[i-1];
for(i=n-1;i>=0;i--)
ord[--f[tp[i]]]=i;
memset(f,0,sizeof(f));
for(i=0;i<n;i++) f[rk[i]]++;
for(i=0;i<=m;i++) f[i]+=f[i-1];
for(i=n-1;i>=0;i--)
sa[--f[rk[ord[i]]]]=ord[i];
f[sa[0]]=1;
for(i=1;i<n;i++)
f[sa[i]]=f[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||tp[sa[i]]!=tp[sa[i-1]]);
for(i=0;i<n;i++)
rk[i]=f[i];
m=rk[sa[n-1]];
}
}
int main()
{
scanf("%s",&s);
n=strlen(s);
m=128;
get_sa();
for(i=0;i<n;i++)
printf("%d ",sa[i]);
return 0;
}
强烈建议你在往下读之前，先刷一遍模板题
洛谷P3809 【模板】后缀排序
未完待续。。