题解-TJOI2015 弦论

TJOI2015 弦论

字符串 \(s\) 和 \(t\) 和 \(k\)。如果 \(t=0\)，不同位置的相同子串算 \(1\) 个；如果 \(t=1\)，不同位置的相同子串算多个。求 \(k\) 小子串，如果不存在输出 \(-1\)。

数据范围：\(1\le n\le 5\cdot 10^5\)，\(t\in\{0,1\}\)，\(1\le k\le 10^9\)。

这题还是很经典的，对理解后缀自动机 \(\tt SAM\) 很有帮助。以前我做过这题（并写了题解），现在复习后缀自动机的时候又做了一次，感悟颇多，遂记之。

首先后缀自动机的节点表示的是一个 \(\bf Endpos\) 集以及该集对应的子串（不一定是后缀）。

一个节点 \(i\) 对应的子串长度范围为 \([len_{fa_i}+1,len_i]\)，即对应子串种数为 \(len_i-len_{fa_i}\)。

同时对应每种子串的数量均为 \(|{\bf Endpos}_i|\) 个。

先看处理这些种数、数量等奇奇怪怪的东西的代码（\(dep\) 即 \(len\)）：

void run(int t){

	for(int i=1;i<=cnt;i++) c[dep[i]]++;

	for(int i=1;i<=cnt;i++) c[i]+=c[i-1];

	for(int i=1;i<=cnt;i++) q[c[dep[i]]--]=i;

	for(int i=cnt;i>=1;i--) sz[fa[q[i]]]+=sz[q[i]]; //①

	for(int i=1;i<=cnt;i++) sm[i]=t?sz[i]:(sz[i]=1); //②

	sz[1]=sm[1]=0;

	for(int i=cnt;i>=1;i--)

		for(int c=0;c<26;c++) sm[q[i]]+=sm[ch[q[i]][c]]; //③

}

这个 \(q\) 数组是对后缀自动机节点按 \(len\) 排序（\(len_i>len_{fa_i}\)）。

①：求出 \(sz_i=|{\bf Endpos}_i|\)。

②：按照题目要求处理。

③：处理子自动机子串数量和 \(sm_i\)，一个 \(|{\bf Endpos}_i|\) 被算 \(len_i-len_{fa_i}\) 次。

至于输出 \(k\) 大子串，一个 \(\tt Dfs\) 的问题。

void Print(int p,int k){

	if(k<=sz[p]) return;

	k-=sz[p];

	for(int c=0;c<26;c++)if(ch[p][c]){

		if(k>sm[ch[p][c]]) k-=sm[ch[p][c]];

		else return void((putchar(c+'a'),Print(ch[p][c],k)));

	}

}

代码

#include <bits/stdc++.h>

using namespace std;

//Start

typedef long long ll;

typedef double db;

#define mp(a,b) make_pair(a,b)

#define x first

#define y second

#define b(a) a.begin()

#define e(a) a.end()

#define sz(a) int((a).size())

#define pb(a) push_back(a)

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

//Data

const int N=5e5;

int n;

char s[N+7];

//SuffuxAutomaton

const int T=N<<1;

int en=1,cnt=1,ch[T+7][26],fa[T+7],dep[T+7]; //dep即len

ll sz[T+7],sm[T+7];

void insert(int c){

	int p=en,np=en=++cnt;

	dep[np]=dep[p]+1;

	for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;

	if(!p) fa[np]=1;

	else {

		int q=ch[p][c];

		if(dep[q]==dep[p]+1) fa[np]=q;

		else {

			int nq=++cnt;

			dep[nq]=dep[p]+1;

			memcpy(ch[nq],ch[q],sizeof ch[q]);

			fa[nq]=fa[q],fa[q]=fa[np]=nq;

			for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;

		}

	}

	sz[np]=1;

}

int c[T+7],q[T+7];

void run(int t){

	for(int i=1;i<=cnt;i++) c[dep[i]]++;

	for(int i=1;i<=cnt;i++) c[i]+=c[i-1];

	for(int i=1;i<=cnt;i++) q[c[dep[i]]--]=i;

	for(int i=cnt;i>=1;i--) sz[fa[q[i]]]+=sz[q[i]];

	for(int i=1;i<=cnt;i++) sm[i]=t?sz[i]:(sz[i]=1);

	sz[1]=sm[1]=0;

	for(int i=cnt;i>=1;i--)

		for(int c=0;c<26;c++) sm[q[i]]+=sm[ch[q[i]][c]];

}

void Print(int p,int k){

	if(k<=sz[p]) return;

	k-=sz[p];

	for(int c=0;c<26;c++)if(ch[p][c]){

		if(k>sm[ch[p][c]]) k-=sm[ch[p][c]];

		else return void((putchar(c+'a'),Print(ch[p][c],k)));

	}

}

//Main

int main(){

	int t,k; scanf("%s%d%d",&s[1],&t,&k),n=strlen(&s[1]);

	for(int i=1;i<=n;i++) insert(s[i]-'a');

	run(t);

	if(sm[1]>=k) Print(1,k); else puts("-1");

	return 0;

}

祝大家学习愉快！

巴特西

题解-TJOI2015 弦论

最新文章

热门文章