[SAM template question] P3975 [TJOI2015] string theory

题目思路

On the original string to establish$SAM$,And then points into cases：

• $t=0$,On behalf of the essence is different,那么我们需要对每个$SAM$节点$u$维护$u$The number of points to reach the,即为经过$u$The nature of the number of different substrings.
• $t=1$,On behalf of the position is different,So we consider for each node$u$Calculate number of substring after that point position is different.Then we can think of this need first string$s$的出现次数,也就是$endpos(s)$的大小,The root to the$u$Said the list of$endpos$大小为$parenttree$上$u$The number of prefix point in the subtree

不难发现,我们可以维护一个$dp[u]$Said the substring under different limit number,And every point, right.对于$t=0$,All right to point point is$1$,否则先$dfs$The right subtree size as point,然后$dfs$And the answer can be.

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;

int dp[N], siz[N];

struct SAM{
    
    int ch[N << 1][26], fa[N << 1], len[N << 1], vis[N << 1];
    int last, tot;
    SAM(): last(1), tot(1) {
    }
    inline void extend(int x){
     //*Single character extension
        int p = last, np = last = ++tot;
        len[np] = len[p] + 1, vis[np] = dp[np] = siz[np] = 1;
        for(; p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
        if(!p) fa[np] = 1;
        else{
    
            int q = ch[p][x];
            if(len[q] == len[p] + 1) fa[np] = q;
            else {
    
                int nq = ++tot;
                memcpy(ch[nq], ch[q], sizeof(ch[nq]));
                fa[nq] = fa[q], fa[np] = fa[q] = nq, len[nq] = len[p] + 1;
                for(; ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
            }
        }
    }
}sam;

vector<int> g[N];

void dfs1(int u){
    
    for(auto v : g[u]){
    
        dfs1(v);
        siz[u] += siz[v];
    }
    dp[u] = siz[u];
}

bool vis[N];

int dfs2(int u){
    
    if(vis[u]) return dp[u];
    vis[u] = true;
    for(int i = 0; i < 26; i++){
    
        int v = sam.ch[u][i];
        if(v) dp[u] += dfs2(v);
    }
    return dp[u];
}

void build(int t){
    
    for(int i = 1; i <= sam.tot; i++){
    
        if(sam.fa[i]) g[sam.fa[i]].emplace_back(i);
    }
    if(!t){
    
        for(int i = 1; i <= sam.tot; i++) dp[i] = siz[i] = 1;
    } else {
    
        dfs1(1);
    }
    dp[1] = siz[1] = 0;
    dfs2(1);
}

void query(int u, int k){
    
    if(k > dp[u]){
    
        cout << -1;
        return;
    }
    if(k <= siz[u]) return;
    k -= siz[u];
    for(int i = 0; i < 26; i++){
    
        int v = sam.ch[u][i];
        if(k > dp[v]) k -= dp[v];
        else{
    
            cout << (char)('a' + i);
            query(v, k);
            return;
        }
    }
}

inline void solve(){
    
    string s; cin >> s;
    for(int i = 0; i < s.size(); i++) sam.extend(s[i] - 'a');
    int t, k; cin >> t >> k;
    build(t);
    query(1, k);
}

signed main(){
    
    //ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}