SA板子+注释

 1 void Suffix_Array(char*a,int n,int m=27){
 2     //变量含义：m是字符集大小，n是字符串长度，c是一个桶数组,a[i]是字符串（下标从1开始）
 3     //sa[i]就是要求的排名为i的后缀的起始位置，即suffix(sa[i])的排名为i
 4     for(int i=1;i<=m;++i) c[i]=0;
 5     for(int i=1;i<=n;++i) x[i]=a[i]-‘a‘+2;
 6     //x[i]用于存储suffix(i)的第一关键字（的排名），在刚开始长度为1的时候就是a[i]
 7     //如果出于某些原因想加入一个空字符（字典序最小），那么在全局把它设置为‘a‘-1就好了，这也是为什么m=27而非26
 8     for(int i=1;i<=n;++i) c[x[i]=a[i]-‘a‘+1]++;
 9     //看起来十分草率的一个扔进桶里的过程
10     for(int i=1;i<=m;++i) c[i]+=c[i-1];
11     //把桶做一遍前缀和。这样操作后就有如果是s[i]=x,则c[x-1]<rk[i]<=c[x]
12     //也就是对于一个c[x-1]<p<=c[x],suffix(sa[p])的第一关键字为x
13     for(int i=1;i<=n;++i) sa[c[x[i]]--]=i;
14     //这句话就是对第10行的那句话的一种实现方式
15     for(int len=1;len<=n;len<<=1){
16         //len表示的是第一关键字与第二关键字分别的长度，所以len<<1就是本轮真正所要比较的长度
17         //定义y数组，表示第二关键字排名为i的后缀是suffix(y[i])
18         int num=0;
19         //num就是用来存储已经排好序的第二关键字的数量
20         for(int i=n-len+1;i<=n;++i) y[++num]=i;
21         //suffix(i)的第二关键字现在是a[i+len...i+2len]。而对于suffix(n-len+1)...suffix(n)已经没有第二关键字了。
22         //而空字符的字典序最小，所以它们第二关键字的排名最靠前
23         for(int i=1;i<=n;++i) if(sa[i]>len) y[++num]=sa[i]-len;
24         //对于所有p>len，a[p...p+len-1]这一截都会成为suffix(p-len)的第二关键字
25         //而你枚举的是sa[i],i从小到大也就是代表你从小到大枚举的所有可能出现的第二关键字
26         //现在y数组里面已经按从小到大的顺序存储好了所有可能出现的第二关键字，包括空的
27         for(int i=1;i<=m;++i) c[i]=0;
28         for(int i=1;i<=n;++i) c[x[i]]++;
29         for(int i=1;i<=m;++i) c[i]+=c[i-1];
30         //都与倍增外面的部分同理。还是按照第一关键字扔桶。下面要基数排序加入第二关键字了。
31         for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i];
32         //这句话是最麻烦的一句，x[y[i]]表示第二关键字排名为i的后缀的第一关键字
33         //注意这里的循环需要倒序，因为你是从大到小枚举第二关键字，而由于你的c[]--，所以得到的排名也是从大到小
34         //这里和第10～11行的注释是同理的，注意每个按关键字排序后的后缀所在的排名区间
35         //所以也可以改写成for(int i=1;i<=n;++i) sa[++c[x[y[i]]-1]]=y[i],y[i]=0;这样全文就都是正序枚举了不易混
36         //我倾向于这个写法，但是还是抄的wzz的原版板子，你们自行选择
37         for(int i=1;i<=n;++i) y[i]=x[i],x[i]=0;
38         //数组的回收利用,只不过是换个数组存了一下第一关键字，清空一个数组备用
39         x[sa[1]]=m=1;
40         //排名最小的串，它在2len长度比较下也最小，所以在下次len<<=1后，它对应的len第一关键字就是最小的第一关键字
41         //这里把m置为1.也就是现在要重新规定字符集大小了，这个1是是x[sa[1]]，m以后表示的就是目前已知的本质不同后缀数
42         for(int i=2;i<=n;++i) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&y[sa[i]+len]==y[sa[i-1]+len])?m:++m;
43         //这时候sa在2len长度的比较下已经排好序了，可以直接按照排名枚举。只要你和你前一名的第一/二关键字不完全相同
44         //那么你们就是不同的，所以你就是一个新串，加入字符集m++，然后重新给它在下一轮的第一关键字编号为m
45         if(m==n)break;
46         //如果你的字符集个数等于后缀个数，那么就是所有的后缀都被两两区分开了，可以提前跳出了
47     }
48     for(int i=1;i<=n;++i)rk[sa[i]]=i;
49     //rk是suffix(i)的排名，从含义上就知道它是sa的逆数组
50 }