后缀排序【后缀数组入门题】

后缀数组真的是好难理解阿，我觉得我一辈子都看不懂了。只能靠模板过日子。

这是一篇我觉得很好的博客：https://www.cnblogs.com/zwfymqz/p/8413523.html#_labelTop

题目链接：https://www.luogu.org/problemnew/show/P3809

题目大意：读入一个长度为

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN = 1e6 + 10;
 6 
 7 char s[MAXN]; //读入字符串 
 8 int N, M, cnt;//N为字符串的长度 len，M为字符串中字符的字符集大小size .
 9 //例如小写字母是26个，大写字母26个，小写+大写就翻倍。暴力点直接用ascii码上限做字符集大小也可以 
10 //cnt是有多少个不同的后缀排序 
11 int rank[MAXN];//以i下标为首的后缀的排名
12 int sa[MAXN];//排名为i的后缀首字符所在下标 
13 int tax[MAXN];//i号元素出现了多少次。辅助基数排序 
14 int tp[MAXN];//基数排序的第二关键字，意义与sa一样，即第二关键字排名为i的后缀首字符所在下标 
15 
16 void Qsort()
17 {
18     for(int i = 0; i <= M; i ++)    tax[i] = 0;
19     for(int i = 1; i <= N; i ++)    tax[rank[i]] ++;
20     for(int i = 1; i <= M; i ++)    tax[i] += tax[i - 1];
21     for(int i = N; i >= 1; i --)    sa[tax[rank[tp[i]]] --] = tp[i];
22 }
23 
24 void get_SA()
25 {
26     for(int i = 1; i <= N; i ++)    rank[i] = s[i] - '0' + 1, tp[i] = i;
27     Qsort();
28     for(int w = 1; w <= N; w *= 2)
29     {
30         cnt = 0;
31         for(int i = 1; i <= w; i ++)    tp[++ cnt] = N - w + i;
32         for(int i = 1; i <= N; i ++)    if(sa[i] > w)    tp[++ cnt] = sa[i] - w;
33         Qsort();
34         swap(tp, rank);
35         rank[sa[1]] = cnt = 1;
36         for(int i = 2; i <= N; i ++)
37             rank[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w]  == tp[sa[i] + w]) ? cnt : ++ cnt;
38         M = cnt;
39         if(cnt == N)
40             break;
41     }
42     for(int i = 1; i <= N; i ++)
43         printf("%d ", sa[i]);
44 }
45 
46 int main()
47 {
48     scanf("%s", s + 1);
49     N = strlen(s + 1);
50     M = 75;
51     get_SA();
52     return 0;
53 }

后缀数组求sa模板