跪谢罗穗骞

Orz__ 一地鸡毛的讲解也很不错。

sa[i] 排名第i的后缀从s[i]位置开始。
rank[i] 第i个位置开始的后缀排名第rank[i]位。
height[i] 排名i位和i-1位的LCA

输入样例

8
aabaaaab

c++代码

我在代码里写了详尽的注释，自己输入样例，看看结果就能理解了。

rank[maxn]在一些编译环境下是ambitiou的，最好替换成其它名字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 5000
#define eps 1e-10
int r[maxn];int n;
int sa[maxn],rank[maxn],height[maxn];
int wa[maxn],wb[maxn],wv[maxn],wss[maxn];
int cmp(int *r,int a,int b,int l){
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i<m;i++) wss[i]=0;
    for(i=0;i<n;i++) wss[x[i]=r[i]]++;
    for(i=1;i<m;i++) wss[i]+=wss[i-1];
    for(i=n-1;i>=0;i--) sa[--wss[x[i]]]=i;
    //上面的这段基数排数可以改成快速排序
    for(j=1,p=1;p<n;j*=2,m=p)
    {
        for(p=0,i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<n;i++) wv[i]=x[y[i]];
        for(i=0;i<m;i++) wss[i]=0;
        for(i=0;i<n;i++) wss[wv[i]]++;
        for(i=1;i<m;i++) wss[i]+=wss[i-1];
        for(i=n-1;i>=0;i--) sa[--wss[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void getHeight(){
   int i,j,k=0;
    for(i=1;i<=n;i++) rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
    return;
}
int main()
{
    cin>>n;getchar();
    for(int i=0;i<n;i++)
        scanf("%c",&r[i]);
    //默认是小写字母
    r[n]='a'-1;
    //在字符串末尾加一个 小于可能出现过的 最小字符还要小的 一个字符
    for(int i=0;i<=n;i++)
        printf(" %d",r[i]);
    //输出ASCII值方便理解
    puts("");
    da(r,sa,n+1,'z'+1);//从左到右分别是，字符串数组，sa数组，
    //字符串长度，一个大于有所出现过字符的值
    cout<<"sa[i] means the ranked i_th substring starts from position of sa[i] "<<endl;
    for(int i=1;i<=n;i++)
        printf("i=%d_%d%c",i,sa[i],i==n?'\n':' ');puts("");
    getHeight();
    cout<<"rank[i] means the substring starts from position i ranked rank[i]_th "<<endl;
    for(int i=0;i<n;i++)
        printf("i=%d_%d%c",i,rank[i],i==n-1?'\n':' ');    puts("");
    cout<<"height[i] means LCA of(sa[i] , sa[i-1])"<<endl;
    for(int i=2;i<=n;i++){
        printf("the %dth & %dth\n",i-1,i);
        for(int j=sa[i-1]; j <n ;j++)
            printf("%c",r[j]);puts("");
        for(int j=sa[i]; j <n ;j++)
            printf("%c",r[j]);puts("");
        printf(" heihgt[%d] ---- %d\n",i,height[i]);
    }
   return 0;
}