bzoj 3998 [TJOI2015]弦论

发表于   |   分类于 ，   |  

先扯几句

昨天tc怎么都上不去，突然想再补补姿势，然后发现SAM这个东西理解的很不到位，花了一晚上重新理解了一下，做了下题来回顾下>_<_

Description

对于一个给定长度为$N$的字符串，求它的第$K$小子串是什么
第二行为两个整数$T$和$K$，$T$为$0$则表示不同位置的相同子串算作一个
$T=1$则表示不同位置的相同子串算作多个,$K$的意义如题所述。
$k\le 5*10^5,N\le 10^9$

Solution

很容易想到用SAM做，$T=1$正常做，$T=0$时考虑right数组的意义，把right数组都赋值为1，拓扑排序处理下即可
最后$dfs$或者非递归处理一下即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
const int N = 500005 * 2, M = 26;
struct SAM {
    int tot, last, step[N], g[N], par[N], son[N][M], cnt[N], Q[N], ch[N], f[N];
    void init() {
        tot = last = 0;
        memset(par, 0, sizeof(par));
        par[0] = -1;
        memset(son, 0, sizeof(son));
    }
    void add(int x) {
        int p = last, np = ++tot;
        step[np] = step[p] + 1, last = np, ++g[np];//right
        ch[np] = x;
        for (; !son[p][x] && ~p; p = par[p])    son[p][x] = np;
        if (p == -1)    return;
        int q = son[p][x];
        if (step[q] == step[p] + 1) par[np] = q;
        else {
            step[++tot] = step[p] + 1;
            ch[tot] = x;
            int nq = tot;
            memcpy(son[nq], son[q], sizeof(son[q]));
            par[nq] = par[q];
            par[np] = par[q] = nq;
            for (; son[p][x] == q && ~p; p = par[p])    son[p][x] = nq;
        }
    }
    void topo() {
        for (int i = 1; i <= tot; ++i)    ++cnt[step[i]];
        for (int i = 1; i <= tot; ++i)    cnt[i] += cnt[i - 1];
        for (int i = 1; i <= tot; ++i)    Q[cnt[step[i]]--] = i;        
    }
    void gao(int t) {
        for (int i = tot; i >= 0; --i) {
            if(t == 0)  g[Q[i]] = 1;
            else g[par[Q[i]]] += g[Q[i]];
            f[Q[i]] = g[Q[i]];
            for (int j = 0; j < 26; ++j)
                f[Q[i]] += f[son[Q[i]][j]];
        }
    }
}S;
char s[N];
int main() {
    scanf("%s", s);
    S.init();
    int l = strlen(s);
    for (int i = 0; i < l; ++i) S.add(s[i] - 'a');
    S.topo();
    int t, k;
    scanf("%d%d", &t, &k);
    S.gao(t);
    int rt = 0, sum = 0;
    for (int i = 0; i < 26; ++i)
        sum += S.f[S.son[0][i]];
    if (k > sum)    puts("-1");
    else {
        while (k) {
            for (int i = 0; i < 26; ++i)
                if (S.son[rt][i]) {
                    if (S.f[S.son[rt][i]] >= k) {
                        printf("%c", 'a' + i);
                        k -= S.g[S.son[rt][i]];
                        rt = S.son[rt][i];
                        break;
                    }
                    else k -= S.f[S.son[rt][i]];
                }
        }
    }
    return 0;
}