题目地址：洛谷：【P3975】[TJOI2015]弦论 – 洛谷、BZOJ：Problem 3998. — [TJOI2015]弦论

题目描述

为了提高智商,ZJY开始学习弦论。这一天,她在《 String theory》中看到了这样一道问题:对于一个给定的长度为n的字符串,求出它的第k小子串是什么。你能帮帮她吗?

题意简述

求一个串的本质不同子串中第k小或所有子串中第k小。

输入输出格式

输入格式：
第一行是一个仅由小写英文字母构成的字符串s
第二行为两个整数t和k,t为0则表示不同位置的相同子串算作一个,t为1则表示不同位置的相同子串算作多个。k的意义见题目描述。

输出格式：
输出数据仅有一行,该行有一个字符串,为第k小的子串。若子串数目不足k个,则输出-1。

输入输出样例

输入样例#1：

aabc
0 3

输出样例#1：

aab

输入样例#2：

aabc
1 3

输出样例#2：

aa

输入样例#3：

aabc
1 11

输出样例#3：

-1

说明

数据范围
对于10%的数据，n ≤ 1000。
对于50%的数据，t = 0。
对于100%的数据，n ≤ 5 × 10^5, t < 2, k ≤ 10^9。

题解

对于SAM来说，这个题是一种经典应用了。
在DAWG上的任何一条从起点出发的路径都是原串的一个子串，因此，如果我们能求出经过一个点的路径数（即DAWG上它能到达的点的数量）就可以知道某一个点的“子树”（由于DAWG并不是严格的树，因此采用这种称呼）中可以表示多少串，从起始点开始往深走就可以求出答案。
对于本质不同的情况，只需把起点到这个点的路径数设置为1，求这个值的“子树和”即可，对于考虑重复的情况，上述值设置为$\mathrm{endpos}$集合大小即可。求和可以用拓扑序（$\max$从大到小的顺序）处理。
这里用了std::sort因此复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <stack>
#include <set>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

const int MAXN = 1000005;

struct SuffixAutomaton {
    int ch[MAXN][26], len[MAXN], nxt[MAXN], siz[MAXN], lst, tot;
    SuffixAutomaton() {
        lst = tot = 1;
    }
    inline void extend(int c) {
        int u = ++tot, v = lst;
        len[u] = len[v] + 1;
        for(; v && !ch[v][c]; v = nxt[v]) ch[v][c] = u;
        if(!v) {
            nxt[u] = 1;
        } else if(len[ch[v][c]] == len[v] + 1) {
            nxt[u] = ch[v][c];
        } else {
            int o = ch[v][c], n = ++tot;
            memcpy(ch[n], ch[o], sizeof(ch[o]));
            len[n] = len[v] + 1;
            for(; v && ch[v][c] == o; v = nxt[v]) ch[v][c] = n;
            nxt[n] = nxt[o]; nxt[o] = nxt[u] = n;
        }
        lst = u; siz[lst] = 1;
    }
} sam;

inline bool cmp(int a, int b) {
    return sam.len[a] > sam.len[b];
}

int n, t, k, a[MAXN], sum[MAXN];
char s[MAXN];

int main() {
    scanf("%s%d%d", s + 1, &t, &k);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i++) {
        sam.extend(s[i] - 'a');
    }
    for(int i = 1; i <= sam.tot; i++) {
        a[i] = i;
    }
    std::sort(a + 1, a + sam.tot + 1, cmp);
    for(int i = 1; i <= sam.tot; i++) {
        if(t) sam.siz[sam.nxt[a[i]]] += sam.siz[a[i]];
        else sam.siz[a[i]] = 1;
    }
    sam.siz[1] = 0;
    for(int i = 1; i <= sam.tot; i++) {
        sum[a[i]] = sam.siz[a[i]];
        for(int j = 0; j < 26; j++) {
            if(sam.ch[a[i]][j]) sum[a[i]] += sum[sam.ch[a[i]][j]];
        }
    }
    if(k > sum[1]) {
        puts("-1"); return 0;
    }
    int p = 1;
    while(k - sam.siz[p] > 0) {
        k -= sam.siz[p];
        int q = 0;
        while(k > sum[sam.ch[p][q]]) k -= sum[sam.ch[p][q++]];
        p = sam.ch[p][q];
        putchar('a' + q);
    }
    return 0;
}