题解 P3975 【[TJOI2015]弦论】

· · 题解

虽然感觉这题已经被人做烂了再发题解也没啥意思了

这篇题解是非bfs版，感觉更好理解也更好写？反正我觉得初学者如果写这种dp的话应该会更容易理解？emm反正比其他题解思路更直观一点。

首先就是SAM就完事儿了。

然后考虑怎么求这个东西，那肯定先在parent树上dp一遍求出来每个子串的出现次数；

但问题是我们如果要像平衡树那样找第k小，求的应该是经过每个点的子串数量，于是就需要在DAG上再dp一遍。

然而上面是老生常谈。由于是DAG，所以想怎么dp怎么dp所以会比较容易，直接dfs就完了，这样感觉思路比较顺

画外音：为啥总感觉这个人在水题解啊？这不就是换了个dp方式吗

我不是我没有……并且感觉这题除了dp还有什么别的值得一提的地方吗？

struct SAM{
    int last, sz ;
    int trans[MAXN][Sigma] ;
    int len[MAXN], fa[MAXN] ;
    void Init(){ last = sz = 1 ; }
    void Insert(int x){
        int np = ++ sz ; 
        int p = last, q, nq ;
        last = np, f[np] = 1 ;
        len[np] = len[p] + 1 ;
        while (p && !trans[p][x]) 
            trans[p][x] = np, p = fa[p] ; 
        if (!p)
            return fa[np] = 1, void() ; 
        q = trans[p][x] ; 
        if (len[q] == len[p] + 1)
            return fa[np] = q, void() ;
        nq = ++ sz, 
        len[nq] = len[p] + 1;
        fa[nq] = fa[q], fa[q] = fa[np] = nq ; 
        memcpy(trans[nq], trans[q], sizeof(trans[q])) ; 
        while (p && trans[p][x] == q) 
            trans[p][x] = nq, p = fa[p] ;
    }
}S;
il void add(int u, int v){
    E[++ ctn].to = v, E[ctn].next = head[u], head[u] = ctn ;
}
void dfs(int u){//第一次的树上dp
    for (int k = head[u] ; k ; k = next(k)) 
        dfs(to(k)), f[u] += f[to(k)] ;
}
void dfs2(int u){//第二次的DAG上dp
    if (vis[u]) return ; vis[u] = 1 ;
    for (int i = 1 ; i <= 26 ; ++ i) 
        if (S.trans[u][i]) 
            dfs2(S.trans[u][i]), g[u] += g[S.trans[u][i]] ;
}
void go_Out(int p, int s){//输出
    if (s <= f[p]) return ; else s -= f[p] ; 
    for (int i = 1 ; i <= 26 ; ++ i)
        if (!S.trans[p][i]) continue ;
        else if (s > g[S.trans[p][i]]) s -= g[S.trans[p][i]] ;
        else { printf("%c", i + 'a' - 1), go_Out(S.trans[p][i], s) ; return ; }
}
int main(){
    cin >> (In + 1) >> T >> K ; 
    N = strlen(In + 1) ; S.Init() ;
    for (int i = 1 ; i <= N ; ++ i) S.Insert(In[i] - 'a' + 1) ; 
    for (int i = 2 ; i <= S.sz ; ++ i) add(S.fa[i], i) ; dfs(1) ;
    for (int i = 1 ; i <= S.sz ; ++ i) g[i] = T ? f[i] : (f[i] = 1) ; 
    f[1] = g[1] = 0, dfs2(1) ; if (K > g[1]) return puts("-1"), 0 ; else return go_Out(1, K), 0 ; 
}

\rm by~Orchidany