前面说了基本的思路模板,现在就可以加一点点应用了~

STEP THREE


题意:
找一下这个string有没有给出的子串~
思路:
已经会将后缀排序了,可以每个后缀串只看要搜索串的长度,再用二分法搜索出来就好啦~

代码在此

#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 += "$";
    int n = s.size();
    vector<int> p(n),c(n);
    {
        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++){
            if(a[i].first == a[i-1].first) {
                c[p[i]] = c[p[i-1]];
            }
            else {
                c[p[i]] = c[p[i-1]] + 1;
            }
        }
    }
    
    int k = 0;
    while((1 << k) < n){

        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++;
    }
    
    int nums;
    cin>>nums;
    while(nums--){
        string checks;
        cin>>checks;
        int s_l = checks.length();
        int l = 0,r = n-1,mid;
        bool is = true;
        while(l <= r){
            mid = (l + r) / 2;
//            cout<<"1 : "<<s.substr(p[mid],s_l) <<"2 : "<< checks<<endl;
            if(s.substr(p[mid],s_l) == checks){
                cout<<"Yes"<<endl;
                is = false;
                break;
            }
            else if(s.substr(p[mid],s_l) > checks){
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if(is) cout<<"No"<<endl;
    }
}

Last modification:July 2nd, 2020 at 10:25 pm
请赏我杯奶茶,让我快乐长肉