某岛

… : "…アッカリ~ン . .. . " .. .
March 21, 2020

Luogu P3975 [TJOI2015]弦论

Luogu 传送门

求 kth 子串。支持区分可重复子串和不可重复子串。


const int N = int(1e6) + 9, Z = 26;

namespace SAM{
    
    int trans[N][Z],par[N],len[N],sum[N],cnt[N],tail,tot;
    char buf[N];
    
    int new_node(){
        RST(trans[tot]);
        return tot++;
    }
    int new_node(int u){
        CPY(trans[tot],trans[u]),par[tot]=par[u];
        return tot++;
    }
#define v trans[u]
#define p par[u]
#define pp par[uu]
    
    int Ext(int c){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = p;
        if (!u && !v) v = uu, pp = 0;
        else{
            if (len[v] == len[u] + 1) pp = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                par[_v] = pp = vv; while (v == _v) v = vv, u = p;
            }
        }
        
        return tail = uu;
    }
    
    int adj[N][26];
    
    void Init(){
        tail = tot = 0; new_node(), RS(buf); REP_S(cur, buf) cnt[Ext(*cur - 'a')] = 1;
        
        static int C[N], Q[N];
        REP(i, tot) ++C[len[i]];
        REP_1(i, len[tail]) C[i] += C[i-1];
        REP(i, tot) Q[--C[len[i]]] = i;
        
        //FOR(u, 1, tot) {
        
        
        
        
        DWN(i, tot, 1) {
            int u = Q[i];
            if (p) cnt[p] += cnt[u];
            //cout << u << " " << cnt[u] << endl;
        }
        
        
        int t; RD(t);
        
        DWN(i, tot, 0){
            int u = Q[i];
            
            if (t == 0) cnt[u] = 1;
            
            int t = 0;
            
          
            sum[u] = cnt[u];
            REP(c, Z) if (v){
                adj[u][t++] = c;
                sum[u] += sum[v];
            }
        }
        
        DWN(u, tot, 0){
            //cnt[p] += cnt[u];
         //   cout << u << " " << sum[u] << " " << cnt[u] << endl;
        }
        cnt[0] = 0;
        
    }
    
#undef c
#define c adj[u][i]
    void kth(int k){
        --k;
        
        if (k >= sum[0]) {
            cout << -1 << endl;
            return;
        }
        
        int u = 0; while (k >= cnt[u]){
            k -= cnt[u]; for (int i=0;;++i){
                if (k >= sum[v]) k -= sum[v];
                else{
                    putchar(c+'a');
                    u = v; break;
                }
            }
        }
        puts("");
    }
    
} using namespace SAM;

int main(){
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    Init(); //Rush kth(RD());
    kth(RD());
    
    
}