bzoj 3998 弦论

Posted on | Views:

$SAM​$ 的入门练习题.

  • 先把 $SAM​$ 建出来,每个节点的 $right​$ 集合大小就是走到这个节点时对应的子串出现次数.
  • 如果 $t=0​$ ,那么这些位置只能被算一次,把每个点的 $right​$ 集合大小都置为 $1​$ ,否则就拓扑排序后(桶排),在$parent​$ 树上递推得出真正的 $right​$ 集合大小.
  • 注意根节点处对应的子串都是空串,不能算入贡献,要把根节点的 $siz$ 置为 $0$ .
  • 再在转移图中递推得到每个点能转移到的所有点的子串出现次数 $sum$ ,然后从根节点出发贪心走就好了.
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
    ll out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        fh=-1,jp=getchar();
    while (jp>='0'&&jp<='9')
        out=out*10+jp-'0',jp=getchar();
    return out*fh;
}
const int Siz=26,MAXN=2e6+10;
int t[MAXN],A[MAXN];
int T,K;
struct SuffixAutomation
{
	int idx,lst;
	int ch[MAXN][Siz];
	int siz[MAXN],len[MAXN];
	int fa[MAXN];
	int sum[MAXN];
	SuffixAutomation(){idx=lst=1;}
	void Extend(int c)
	{
		int p=lst,np=++idx;
		lst=np;
		siz[np]=1;
		len[np]=len[p]+1;
		while(p && ch[p][c]==0)
			ch[p][c]=np,p=fa[p];
		if(p==0)
			fa[np]=1;
		else
		{
			int q=ch[p][c];
			if(len[q]==len[p]+1)
				fa[np]=q;
			else
			{
				int nq=++idx;
				len[nq]=len[p]+1;
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				memcpy(ch[nq],ch[q],sizeof ch[q]);
				while(p && ch[p][c]==q)
					ch[p][c]=nq,p=fa[p];
			}
		}
	}
	void solve()
	{
		for(int i=1;i<=idx;++i)
			++t[len[i]];
		for(int i=1;i<=idx;++i)
			t[i]+=t[i-1];
		for(int i=1;i<=idx;++i)
			A[t[len[i]]--]=i;
		if(T==0)
		{
			for(int i=1;i<=idx;++i)
				siz[i]=1;
		}
		else
		{
			for(int i=idx;i>=1;--i)
			{
				int u=A[i];
				siz[fa[u]]+=siz[u];
			}
		}
		siz[1]=0;//在根节点处的串都是空串,不能计入 
		for(int i=idx;i>=1;--i)
		{
			int u=A[i];
			sum[u]=siz[u];
			for(int j=0;j<26;++j)
				if(ch[u][j])
					sum[u]+=sum[ch[u][j]];
		}
		int u=1;
		if(sum[u]<K)
		{
			puts("-1");
			return;
		}
		while(K)
		{
			for(int i=0;i<Siz;++i)
			{
				if(K<=sum[ch[u][i]])
				{
					putchar('a'+i);
					K-=siz[ch[u][i]];
					u=ch[u][i];
					break;
				}
				else
					K-=sum[ch[u][i]];
			}
		}
		puts("");
	}
}SAM;
char buf[MAXN];
int main()
{
	scanf("%s",buf+1);
	int L=strlen(buf+1);
	for(int i=1;i<=L;++i)
		SAM.Extend(buf[i]-'a');
	T=read(),K=read();
	SAM.solve();
    return 0;
}