今天去CF刷并查集，结果被EDU所吸引，点进去不亏啊！
第一节课讲解的是后缀--Suffix Array
介绍
简而言之就是，给一个字串，将每一位的后缀按字典序排列。
课程内容一共是5个step，前两个是基本的模板，后三个是应用（还没看）
听了一二节，老师牛啊，我这种几乎不会什么算法的都懂了 
跟着老师经历了一遍优化算法的过程！真是美妙而神奇的旅程hhhh
STEP ONE
算法想出来时还没优化就长这个样~
思路：
看2^k个字符，k从0开始递增。字串后面加上'$'以便于成环比较大小。
首先 k = 0 时，第i位（p[i]）按s[i]进行等级划分得到c[i]。
接着，k > 0 时，将2^k个字符对半分，分别按照前面得到的p[i]与c[i]对应的等级规律得到pair，排序后重新产生新的等级规律。
代码在此
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
s += "$";
// cout<<s<<endl;
int n = s.size();
vector<int> p(n),c(n);
{
//k = 0
vector<pair<char,int>> a(n);
for(int i = 0;i < n;i++) a[i] = {s[i],i};
sort(a.begin(),a.end());
for(int i = 0;i < n;i++) p[i] = a[i].second;
/*classify*/
c[p[0]] = 0;
for(int i = 1;i < n;i++){
// cout<<a[i].first<<" "<<a[i-1].first<<endl;
if(a[i].first == a[i-1].first) {
c[p[i]] = c[p[i-1]];
// cout<<"c[p[i]] = c[p[i-1]]"<<c[p[i]] <<" "<< c[p[i-1]]<<endl;
}
else {
c[p[i]] = c[p[i-1]] + 1;
}
// cout<<"p["<<i-1<<"]"<<" , "<<"c["<<p[i-1]<<"]"<<" = "<<c[p[i-1]]<<endl;
}
// cout<<"c[p[4]] = "<<c[p[4]]<<endl;
}
int k = 0;
while((1 << k) < n){
//k -> k+1
vector<pair<pair<int,int>,int>> A(n);
for(int i = 0;i < n;i++){
A[i] = {{c[i],c[(i+(1 << k)) % n]},i};
}
sort(A.begin(),A.end());
for(int i = 0;i < n;i++) p[i] = A[i].second;
/*classify*/
c[p[0]] = 0;
for(int i = 1;i < n;i++){
if(A[i].first == A[i-1].first) c[p[i]] = c[p[i-1]];
else c[p[i]] = c[p[i-1]] + 1;
}
k++;
}
for(int i = 0;i < n;i++){
cout<<p[i]<<" "<<s.substr(p[i],n-p[i])<<endl;
}
}注：一定要注意j = i++; 和j = i + 1;的区别 
前面的i也加了，就因为没注意写顺手了浪费了好多时间..
还有就是vector<....> a(n) 是小括号哼！
STEP TWO
进行一些算法的优化！之前的算法是用sort排序pair<int,int>的，
但是对于这样数在一定范围内int的pair可以用Radix Sort排序节省时间！
思路：
首先只看second，计算有相同的second的pair个数，并将他们划分进一个区域里。
再只看first数，同样计算有相同的first的pair个数，并将他们划分进一个区域里。
这样就按顺序排列好啦~
改进后代码在此
#include <bits/stdc++.h>
using namespace std;
void Radix_sort(vector<pair<pair<int,int>,int>> &a){
int n = a.size();
{
vector<int> cnt(n);
for(auto x:a){
cnt[x.first.second] ++ ;
}
vector<pair<pair<int,int>,int>> a_new(n);
vector<int> pos(n);
pos[0] = 0;
for(int i = 1;i < n;i++){
pos[i] = pos[i-1] + cnt[i-1];
}
for(auto x : a){
int i = x.first.second;
a_new[pos[i]] = x;
pos[i] ++ ;
}
a = a_new;
}
{
vector<int> cnt(n);
for(auto x:a){
cnt[x.first.first] ++ ;
}
vector<pair<pair<int,int>,int>> a_new(n);
vector<int> pos(n);
pos[0] = 0;
for(int i = 1;i < n;i++){
pos[i] = pos[i-1] + cnt[i-1];
}
for(auto x : a){
int i = x.first.first;
a_new[pos[i]] = x;
pos[i] ++ ;
}
a = a_new;
}
}
int main()
{
string s;
cin>>s;
s += "$";
// cout<<s<<endl;
int n = s.size();
vector<int> p(n),c(n);
{
//k = 0
vector<pair<char,int>> a(n);
for(int i = 0;i < n;i++) a[i] = {s[i],i};
sort(a.begin(),a.end());
for(int i = 0;i < n;i++) p[i] = a[i].second;
/*classify*/
c[p[0]] = 0;
for(int i = 1;i < n;i++){
// cout<<a[i].first<<" "<<a[i-1].first<<endl;
if(a[i].first == a[i-1].first) {
c[p[i]] = c[p[i-1]];
// cout<<"c[p[i]] = c[p[i-1]]"<<c[p[i]] <<" "<< c[p[i-1]]<<endl;
}
else {
c[p[i]] = c[p[i-1]] + 1;
}
// cout<<"p["<<i-1<<"]"<<" , "<<"c["<<p[i-1]<<"]"<<" = "<<c[p[i-1]]<<endl;
}
// cout<<"c[p[4]] = "<<c[p[4]]<<endl;
}
int k = 0;
while((1 << k) < n){
//k -> k+1
vector<pair<pair<int,int>,int>> A(n);
for(int i = 0;i < n;i++){
A[i] = {{c[i],c[(i+(1 << k)) % n]},i};
}
////////////////////Radix Sort
Radix_sort(A);
for(int i = 0;i < n;i++) p[i] = A[i].second;
/*classify*/
c[p[0]] = 0;
for(int i = 1;i < n;i++){
if(A[i].first == A[i-1].first) c[p[i]] = c[p[i-1]];
else c[p[i]] = c[p[i-1]] + 1;
}
k++;
}
for(int i = 0;i < n;i++){
cout<<p[i]<<" "<<s.substr(p[i],n-p[i])<<endl;
}
}
SETP TWO PLUS
排好 k = 0 后，在以后的排列中可以发现，将另一半直接写到 k = 0 （上一级k）的前面，再将对应的p[i]值减去加上的字符数。新的p[i]按照对应的等级计算好后与上一级k的结果合并出的pair中，second元素已经按顺序排好啦~因此只要拍first就可以了！
最终版代码在此
#include <bits/stdc++.h>
using namespace std;
void count_sort(vector<int> &p,vector<int> &c){
int n = p.size();
vector<int> cnt(n);
for(auto x:c){
cnt[x] ++ ;
}
vector<int> p_new(n);
vector<int> pos(n);
pos[0] = 0;
for(int i = 1;i < n;i++){
pos[i] = pos[i-1] + cnt[i-1];
}
for(auto x : p){
int i = c[x];
p_new[pos[i]] = x;
pos[i] ++ ;
}
p = p_new;
}
int main()
{
string s;
cin>>s;
s += "$";
// cout<<s<<endl;
int n = s.size();
vector<int> p(n),c(n);
{
//k = 0
vector<pair<char,int>> a(n);
for(int i = 0;i < n;i++) a[i] = {s[i],i};
sort(a.begin(),a.end());
for(int i = 0;i < n;i++) p[i] = a[i].second;
/*classify*/
c[p[0]] = 0;
for(int i = 1;i < n;i++){
// cout<<a[i].first<<" "<<a[i-1].first<<endl;
if(a[i].first == a[i-1].first) {
c[p[i]] = c[p[i-1]];
// cout<<"c[p[i]] = c[p[i-1]]"<<c[p[i]] <<" "<< c[p[i-1]]<<endl;
}
else {
c[p[i]] = c[p[i-1]] + 1;
}
// cout<<"p["<<i-1<<"]"<<" , "<<"c["<<p[i-1]<<"]"<<" = "<<c[p[i-1]]<<endl;
}
// cout<<"c[p[4]] = "<<c[p[4]]<<endl;
}
int k = 0;
while((1 << k) < n){
//k -> k+1
// vector<pair<pair<int,int>,int>> A(n);
// for(int i = 0;i < n;i++){
// A[i] = {{c[i],c[(i+(1 << k)) % n]},i};
// }
for(int i = 0;i < n;i++){
p[i] = (p[i] - (1 << k) + n) % n;
}
count_sort(p,c);
/*classify*/
vector<int> c_new(n);
c_new[p[0]] = 0;
for(int i = 1;i < n;i++){
pair<int,int> now = {c[p[i]],c[(p[i] + (1 << k)) % n]};
pair<int,int> prev = {c[p[i-1]],c[(p[i-1] + (1 << k)) % n]};
if(now == prev) c_new[p[i]] = c_new[p[i-1]];
else c_new[p[i]] = c_new[p[i-1]] + 1;
}
c = c_new;
k++;
}
for(int i = 0;i < n;i++){
cout<<p[i]<<" "<<s.substr(p[i],n-p[i])<<endl;
}
}
今天
好不容易听明白了，对老师的这些代码也没啥改动和改进 
不过确实学到了些知识（也不知道对以后学习有没有帮助）
但是我想其实很多学到的知识，可能以后都不会用到吧，就像观星和艺术，只不过是因为喜欢这东西所以来学习~
所以虽然学了这算法，还要改进优化，有没有用喜欢就好！（大一的我还有机会放荡几天）
今天考完了模电，好难啊，呜呜呜呜呜呜呜呜呜呜呜 
明天晚上考试大物，明天一天都要补天了...
7.4还要高数，更慌，这学期没咋学，就靠后两天了！
冲鸭！！！睡觉去了~ 明天大物莫得问题！
