[TJOI2015]弦论

题目描述

Luogu 3975
BZOJ 3998
求一个串的第k小子串，不同位置的相同的子串算作一个或多个。

题解

看到子串就会想到后缀自动机，其实这个题只是一个后缀自动机的简单应用，只要运用一个搜索树的思想找第k个子串即可。
如果重复的子串算作一个的话，那就不用求endpos，直接设为1即可。否则就要求出endpos。
至于如何求某个节点x“后面”的子串数tot，就只用对tot[trans[x][i]]求和即可。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>

const int M = 1e6 + 10;
const int N = 5e5 + 10;

char s[N];
int trans[M][26], slink[M], maxlen[M], minlen[M], gr[M], ep[M], tot[M];
int len, n;
int tmp[N], rnk[M];
int t, k;

inline int new_state(int mx, int mn, int *tr, int sl) {
    maxlen[n] = mx; minlen[n] = mn; slink[n] = sl;
    for (int i = 0; i < 26; ++i) {
        if (tr == NULL) trans[n][i]=-1;
        else trans[n][i] = tr[i];
    }
    return n++;
}

inline void link(int x, int y) {
    minlen[x] = maxlen[y]+1; slink[x] = y; deg[y]++;
}

inline int addc(int c, int u) {
    int z = new_state(maxlen[u]+1, -1, NULL, -1);
    gr[z] = 1;
    while (u != -1 && trans[u][c] == -1) {
        trans[u][c] = z;
        u = slink[u];
    }
    if (u == -1) {
        link(z, 0);
        return z;
    }
    int x = trans[u][c];
    if (maxlen[x] == maxlen[u]+1) {
        link(z, x);
        return z;
    }
    int y = new_state(maxlen[u]+1, minlen[x], trans[x], slink[x]);
    link(x, y);
    link(z, y);
    while (u != -1 && trans[u][c] == x) {
        trans[u][c] = y;
        u = slink[u];
    }
    return z;
}

inline void build() {
    int u = new_state(0, 0, NULL, -1);
    for (int i = 0; i < len; ++i) u = addc(s[i]-'a', u);
    
    for (int i = 0; i < n; ++i) tmp[maxlen[i]]++;
    for (int i = 1; i <= len; ++i) tmp[i] += tmp[i-1];
    for (int i = 0; i < n; ++i) rnk[tmp[maxlen[i]]--] = i;
    for (int i = n; i; --i) {
        int &j = rnk[i];
        ep[j] += gr[j];
        if (!t) ep[j] = 1;
        else if (slink[j] != -1) ep[slink[j]] += ep[j];
    }
    ep[0] = 0;
    for (int i = n; i; --i) {
        int &j = rnk[i];
        tot[j] = ep[j];
        for (int c = 0; c < 26; ++c) if (trans[j][c] != -1) 
            tot[j] += tot[trans[j][c]];
    }
}

int main() {
    scanf("%s", s);
    len = strlen(s);
    scanf("%d%d", &t, &k);
    build();
    int x = 0;
    if (k > tot[0]) {
        puts("-1");
        return 0;
    }
    while (1) {
        for (int i = 0; i < 26; ++i) if (trans[x][i] != -1) {
            int &y = trans[x][i];
            if (k <= tot[y]) {
                printf("%c", i+'a');
                if (k <= ep[y]) return 0;
                k -= ep[y];
                x = y; 
                break;
            } else k -= tot[y];
        }
    }
    
    return 0;
}