后缀数组
顾名思义，后缀数组就是对一个字符串的每个后缀的排名，这个排名是从小到大排的，显然不会有两个后缀相等。
那么介绍几个变量：
首先每个后缀我们用它第一个字符的下标来唯一的表示了。
SA[]:这就是最终所得到的数组，SA[i]表示第i小的后缀。它满足Suffix(SA[i])<Suffix(SA[i+1])。数组值一直更新。
Rank[]:名次数组，Rank[i]表示的是以i开头的后缀是第几大。Rank和SA互逆。数组值一直更新。
这两个数组，一个是根据排名大小对后缀下标排序，一个是根据后缀下标大小对排名排序，二者都是从小到大排。
这是两个最主要的变量，下面在处理细节时还会用到一些中间变量，等用到的时候在具体介绍。
拿一张被盗了好多次的图来解释这两个变量：
倍增
接下来讲这个算法大致实现的过程：主要思想是倍增算法。
用倍增的方法对从每个字符开始的长度为2^{k}的子串进行排序，每个子串的结尾不要超过母串的结尾时。这样就可以用O(nlogn)的复杂度对所有后缀排序了。在每一次对长度为2^{k-1}的子串排好序之后，得到一些关键字(即排序的名次)，这些关键字作为第一关键字，然后该字符后的第2^{k-1}个字符的关键字作为第二关键字，根据这两个关键字进行排序(第一关键字的优先级大于第二)。这样就在2^{k-1}的基础上完成了2^{k}的排序。若超过了串尾，则第二关键字为0。
这样就可以在O(nlogn)的时间复杂度下完成所有后缀的排序。容易发现，在第一个字符为首的子串到达串尾时，所有子串的名次一定会各不相同，中间过程中可能会有相同的出现。
接下来再来看对两个关键字排序的问题，方法很多，比如写进一个结构体直接sort，但是，加上需要排序的次数和每次排序的时间，时间复杂度为n(logn)^2，这样还是太慢了，用sort未免会有些小题大做，因为只有两个关键字，且数据的范围也是可以确定的(排名的名次，数值当然不会太大)，当数据不大时，不禁想到了一种人见人爱的排序方法--"桶"排。所以这里介绍一种和桶排有关系的新算法---基数排序。
变量名：
Rank[]：第一关键字，表示第i个下标的排名，存的是排名名次。数组值一直更新。
tp[]：存放的是第二关键字中，排名为i的下标，注意存的是下标。数组值一直更新。
在每次基数排序之前，一定注意，存放第一关键字的数组Rank存的是排名名次，存放第二关键字的数组tp存放的是下标。
再次声明RSort的作用：两个存放第一二关键字的数组ab都没改变，改变的SA，SA更新为建立在ab的基础上的新的第一关键字！
基数排序其实还不是特别清晰，以后再写吧。。。。。
height数组
还有一个重要应用---height数组
height[]:height[i]表示Suffix[SA[i]]和Suffix[SA[i-1]]的LCP，即大小相邻的两个后缀的最大公共前缀。注意是和前一名。
H[]:H[i]=Height[Rank[i]],即下标为i的后缀和排在它前一位的后缀的LCP
重要性质：H[i] >= H[i-1]+1
证明：我们假设Suffix[i-1]的排名上一位的后缀为Suffix[k1]，Suffix[i]的排名上一位的后缀为Suffix[k2]，现在去掉Suffix[i-1]的第一个字符，变成了Suffix[i]，Suffix[i]和Suffix[k1]的LCP为H[i-1]-1，这个是显然易见的。我们还知道什么呢？Suffix[k2]可能不等于Suffix[k1]，但是Suffix[k2]和Suffix[i]的LCP一定不比Suffix[k1]和Suffix[i]的LCP小。所以有H[i]>=H[i-1]+1...就这样。利用的性质就是，排名越相近的两个后缀，它们的LCP就越大。
那么有初始条件height[1] = 0,可以用O(n)的复杂度求出height
和求kmp中next的作法有点像。。
void GetHeight(){
int j,k=0;
for (int i=1;i<=n;i++){
if (k) k--;
j = SA[Rank[i]-1];
while (s[i+k]==s[j+k]) k++;
Height[Rank[i]] = k;
}
}很绕，以后要多来看看，多想想细节！
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
int SA[maxn],Rank[maxn],tp[maxn],tax[maxn];
char s[maxn];
int n,m;
void GetSA(int a[],int b[]); //a 第一关键字 b 第二关键字
void RSort(int a[],int b[]);
int main(){
scanf ("%s",s+1);
n = strlen(s+1);
GetSA(Rank,tp);
for (int i=1;i<=n;i++){
printf ("%d",SA[i]);
if (i!=n) putchar(' ');
}
return 0;
}
void GetSA(int a[],int b[]){
for (int i=1;i<=n;i++) a[i] = s[i],b[i] = i; //第一关键字就先等于这个字符的大小，第二关键字由于都是0，所以排序后就按下标大小给了
m = 130; //m的职责是 每次排名后名次的最大值
RSort(a,b);
for (int p,k=1;p!=n;k<<=1,m=p){ //m==n后，排序结束！ //在每一轮循环结束后，SA值已更新为最新的第一关键字，然后就该更新b第二关键字了。
p = 0;
for (int i=n+1-k;i<=n;i++) b[++p] = i;
for (int i=1;i<=n;i++) if (SA[i]>k) b[++p] = SA[i]-k; //既然SA中有已经排序好的第一关键字，那第二关键字自然就顺序的从中挑选就行了。
RSort(a,b); swap(a,b); //1
a[SA[1]] = p = 1;
for (int i=2;i<=n;i++)
a[SA[i]] = (b[SA[i]]==b[SA[i-1]] && b[SA[i]+k]==b[SA[i-1]+k])?p:++p; //1不是特别清楚！
}
return;
}
void RSort(int a[],int b[]){ //RSort前，a和SA都是第一关键字(不同版本)，排序后，SA里的第一关键字更新了，ab都没变。
for (int i=1;i<=m;i++) tax[i] = 0;
for (int i=1;i<=n;i++) tax[a[i]]++; //这一步，经测试，tax[a[b[i]]]++;也正确，据说还是正解。。
for (int i=1;i<=m;i++) tax[i] += tax[i-1];
for (int i=n;i>=1;i--) SA[tax[a[b[i]]]--] = b[i]; //2一个点未搞定
}模板
这里再贴一下实战时会使用的最新的板子
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e4+5;
typedef struct SA{
int SA[maxn],Rank[maxn],tp[maxn],tax[maxn],Height[maxn];
int n,m;
char s[maxn];
void build(){
m = 130;
n = strlen(s+1);
GetSA(Rank,tp);
GetHeight();
}
void GetSA(int a[],int b[]);
void RSort(int a[],int b[]);
void GetHeight();
int check(int i);
}SA;
SA a;
int ans;
int main(){
scanf ("%s",a.s+1);
a.build();
return 0;
}
void SA::GetHeight(){
int j,k=0;
for (int i=1;i<=n;i++){
if (k) k--;
j = SA[Rank[i]-1];
while (s[i+k]==s[j+k]) k++;
Height[Rank[i]] = k;
}
return;
}
void SA::GetSA(int a[],int b[]){
for (int i=1;i<=n;i++) a[i] = s[i],b[i] = i;
RSort(a,b);
int p=0,k=1;
for (;p!=n;k<<=1,m=p){
p = 0;
for (int i=n+1-k;i<=n;i++) b[++p] = i;
for (int i=1;i<=n;i++) if (SA[i]>k) b[++p] = SA[i]-k;
RSort(a,b); swap(a,b);
a[SA[1]] = p = 1;
for (int i=2;i<=n;i++)
a[SA[i]] = (b[SA[i]]==b[SA[i-1]] && b[SA[i]+k]==b[SA[i-1]+k])?p:++p;
}
for (int i=1;i<=n;i++) Rank[SA[i]] = i; //这一步！因为GetSA函数只能保证SA数组完全正确，在赋值完成后最好在给Rank数组再赋一次值
return;
}
void SA::RSort(int a[],int b[]){
for (int i=1;i<=m;i++) tax[i] = 0;
for (int i=1;i<=n;i++) tax[a[b[i]]]++;
for (int i=1;i<=m;i++) tax[i] += tax[i-1];
for (int i=n;i>=1;i--) SA[tax[a[b[i]]]--] = b[i];
return;
}应用
任意两个后缀的LCP
在SA上建立线段树，假定两个后缀为i，j，那么它们的LCP应为min{Height[Rank[i]~Rank[j]]}.也就是他俩的排名所构成的范围内，Height的最小值。
用线段树可能有点大材小用了，rmp也能做。
可重叠最长重复子串
也就是出现次数不止一次的最长的子串，其实就是Height里的最大值啦。
不可重叠最长重复子串 POJ1743
有时间看一下
本质不同的子串
枚举每个后缀，后缀i对答案的贡献是len-i-Height[i]，len-i为后缀i的长度。
0 条评论