今天去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,排序后重新产生新的等级规律。
STEP I 直观

代码在此

#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个数,并将他们划分进一个区域里。
这样就按顺序排列好啦~
Radix Sort

改进后代码在此

#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就可以了!
Count Sort

最终版代码在此

#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还要高数,更慌,这学期没咋学,就靠后两天了!
冲鸭!!!睡觉去了~ 明天大物莫得问题!

Last modification:July 4th, 2020 at 12:32 am
请赏我杯奶茶,让我快乐长肉