SA詳細注記非圧行コード
1 void Suffix_Array(char*a,int n,int m=27){
2 // ：m ，n ，c ,a[i] （ 1 ）
3 //rk[i] suffix(i) ，sa[i] i ， rk[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 // ， i ， ！！！
8 // （ ）， 'a'-1 ， m=27 26
9 for(int i=1;i<=n;++i) c[x[i]]++;
10 //
11 for(int i=1;i<=m;++i) c[i]+=c[i-1];
12 // 。 s[i]=x, c[x-1]13 // c[x-1]
14 for(int i=1;i<=n;++i) sa[c[x[i]]--]=i;
15 // 12～13
16 for(int len=1;len<=n;len<<=1){
17 //len ， len<<1
18 // y ， i suffix(y[i])
19 int num=0;
20 //num
21 for(int i=n-len+1;i<=n;++i) y[++num]=i;
22 //suffix(i) a[i+len...i+2len-1]。 suffix(n-len+1)...suffix(n) 。
23 // ，
24 for(int i=1;i<=n;++i) if(sa[i]>len) y[++num]=sa[i]-len;
25 // p>len，a[p...p+len-1] suffix(p-len)
26 // sa[i],i
27 // y ，
28 // y ， x ，x i ，y i
29 for(int i=1;i<=m;++i) c[i]=0;
30 for(int i=1;i<=n;++i) c[x[i]]++;
31 for(int i=1;i<=m;++i) c[i]+=c[i-1];
32 // 。 。 。
33 for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i];
34 // ，x[y[i]] i
35 // ， ， c[]--，
36 // 12～13 ，
37 // for(int i=1;i<=n;++i) sa[++c[x[y[i]]-1]]=y[i]; , c[0]
38 // ， AC。 wzz ，
39 for(int i=1;i<=n;++i) y[i]=x[i],x[i]=0;
40 // , ，
41 x[sa[1]]=m=1;
42 // ， 2len ， len<<=1 ， len
43 // m 1. ， 1 x[sa[1]]，m
44 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;
45 // sa 2len ， 。 /
46 // ， ， m++， m
47 if(m==n)break;
48 // ， ，
49 }
50 for(int i=1;i<=n;++i)rk[sa[i]]=i;
51 //rk suffix(i) ， sa
52 }