弦论

Time Limit: 10 Sec Memory Limit: 256 MB

Description

对于一个给定长度为N的字符串，求它的第K小子串是什么。

Input

第一行是一个仅由小写英文字母构成的字符串S。
　　第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。
　　T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

Sample Input

aabc
　0 3

Sample Output

aab

HINT

N<=5*10^5, T<2, K<=10^9

Solution

首先我们先构造一个后缀自动机，然后分类讨论：

1. 如果T=0，点权为1。为什么呢？一个点有一个Right集合，一个Right集合可以表达多个子串 ，然后我们一个点 -> 另外一个点 其实不止一条边，我们每条边涵盖了一个信息，意味着 这个点->(走这条边)->到达了下一个点 通过这条边得到的那个新子串，而这多个新子串构成了一个 新的点。所以一条合法的路径，就表达了一个子串。

2. 如果T=1，点权为Right集合大小。Right集合是结束位置的合集，那么Right集合大小就表示这条路径表达的这个子串出现了多少次。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 2e6+5;

int n,T,k;
char ch[500005];

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

struct SAM
{
    int v[500005], q[ONE], num[ONE], size[ONE];
    int a[ONE][28], len[ONE], fa[ONE], New;
    int last, cnt;

    SAM() {last = cnt = 1;}
    void Add(int c)
    {
        int x=last, New=last=++cnt;
        len[New] = len[x] + 1;
        num[New] = 1;
        while(x && !a[x][c]) a[x][c] = New, x = fa[x];
        if(!x) {fa[New] = 1; return;}

        int q = a[x][c];
        if(len[x] + 1 == len[q]) fa[New] = q;
        else
        {
            int Nq = ++cnt; len[Nq] = len[x] + 1;
            memcpy(a[Nq], a[q], sizeof(a[q]));
            fa[Nq] = fa[q];
            fa[New] = fa[q] = Nq;
            while(a[x][c] == q) a[x][c] = Nq, x = fa[x];
        }
    }

    void Update()
    {
        for(int i=1;i<=cnt;i++) v[len[i]]++;
        for(int i=1;i<=n;i++) v[i] += v[i-1];
        for(int i=cnt;i>=1;i--) q[v[len[i]]--] = i;


        for(int i=cnt; i>=1; i--)
        {
            int x = q[i];
            if(!T) num[x] = 1; else num[fa[x]] += num[x];
        }
        num[1] = 0;

        for(int i=cnt; i>=1; i--)
        {
            int x = q[i];
            size[x] = num[x];
            for(int j=1; j<=26; j++)
                size[x] += size[a[x][j]];
        }
    }

    void Dfs(int u,int k)
    {
        if(k <= num[u]) return;
        k -= num[u];
        for(int j=1; j<=26; j++)
            if(a[u][j])
            {
                if(k > size[a[u][j]]) k -= size[a[u][j]];
                else
                {
                    printf("%c",j+'a'-1);
                    Dfs(a[u][j], k);
                    return;
                }
            }
    }
}S;

int main()
{
    scanf("%s",ch+1); n = strlen(ch+1);
    T = get();    k = get();
    for(int i=1;i<=n;i++) S.Add(ch[i]-'a'+1);

    S.Update();

    if(k > S.size[1]) printf("-1");
    else S.Dfs(1, k);

}