BZOJ3998【TJOI2015】弦论 <后缀自动机>

Posted on Symbols count in article: 687 Reading time ≈ 2 mins.

Problem

【TJOI2015】弦论

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

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

Input

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

Output

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

Sample Input

1
2
aabc
0 3

Sample Output

1
aab

标签：后缀自动机

Solution

后缀自动机的模板题。

对于两个询问的找到第KK大，预处理出从每个状态节点向后有多少种符合规则的字符串，然后每次选择走哪个字符即可。

关于预处理：

  • 对于T=0T=0，即计算后缀自动机所形成的DAGDAG上有多少条从初始状态出发路径，将每一个状态节点初值赋为11后按拓扑序在DAGDAG上DPDP即可。
  • 对于T=1T=1，类似上面，也是按拓扑序在DAGDAG上作DPDP，只是此时只有表示原字符串每个前缀结束状态的节点的初值为11。

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
#include <bits/stdc++.h>
#define MAX_N 500000
using namespace std;
char s[MAX_N+5];    int l, T, K, tot[MAX_N+5];
int rt, sz, lst, val[(MAX_N<<1)+5], sum[(MAX_N<<1)+5];
struct node {int ch[26], len, par;} SAM[(MAX_N<<1)+5];
int newnode(int _len) {SAM[++sz].len = _len; return sz;}
void init() {sz = 0, rt = lst = newnode(0);}
void insert(int c) {
    int p = lst, np = newnode(SAM[p].len+1); lst = np, val[np] = 1;
    for (; p && !SAM[p].ch[c]; p = SAM[p].par) SAM[p].ch[c] = np;
    if (!p) {SAM[np].par = rt; return;}	int q = SAM[p].ch[c];
    if (SAM[q].len == SAM[p].len+1) {SAM[np].par = q; return;}
    int nq = newnode(SAM[p].len+1);
    memcpy(SAM[nq].ch, SAM[q].ch, sizeof SAM[q].ch);
    SAM[nq].par = SAM[q].par, SAM[q].par = SAM[np].par = nq;
    for (; p && SAM[p].ch[c] == q; p = SAM[p].par) SAM[p].ch[c] = nq;
}
int prt(int c, int k) {
    if (k <= val[c]) return 1;	k -= val[c];
    for (int i = 0; i < 26 && k > 0; k -= sum[SAM[c].ch[i++]])
        if (SAM[c].ch[i] && k <= sum[SAM[c].ch[i]])
            putchar('a'+i), prt(SAM[c].ch[i], k);
    return 1;
}
int main() {
    int que[(MAX_N<<1)+5];	init();
    scanf("%s%d%d", s, &T, &K), l = (int)strlen(s);
    for (int i = 0; i < l; i++) insert(s[i]-'a');
    for (int i = 1; i <= sz; i++) tot[SAM[i].len]++;
    for (int i = 1; i <= l; i++) tot[i] += tot[i-1];
    for (int i = sz; i; i--) que[tot[SAM[i].len]--] = i;
    for (int i = sz; i; i--)
        if (!T) val[que[i]] = 1;
        else val[SAM[que[i]].par] += val[que[i]];
    val[1] = 0;
    for (int i = 1; i <= sz; i++) sum[i] = val[i];
    for (int i = sz; i; i--) for (int j = 0; j < 26; j++)
        sum[que[i]] += sum[SAM[que[i]].ch[j]];
    return (K > sum[rt] ? puts("-1") : prt(rt, K)), 0;
}