BZOJ3998

来自蒟蒻XXJ的做题记录

日常BZOJ乱翻水题的时候翻到了这个题目==

然后发现这个东西是个SAM的裸板子 好开心好开心

然后T=0用1表示每个state的出现次数 因为不计重复

T=1时用每个state的right数组表示出现次数就好了

然后求和 再走一走

#include<bits/stdc++.h>
#define mem(i,j) memset(i,j,sizeof(i))
#define mcy(i,j) memcpy(i,j,sizeof(i))
using namespace std;
const int MAXN=1000010;
struct SAM{
	int trans[MAXN][26],fa[MAXN],lth[MAXN],r[MAXN],s[MAXN],siz[MAXN];
	int cnt,last;
	SAM(){
		cnt=0;last=++cnt;
		mem(trans,0);mem(fa,0);mem(lth,0);mem(r,0);mem(s,0);mem(siz,0);
	}
	void extend(int c){
		int np=++cnt,p=last;last=cnt;
		lth[np]=lth[p]+1;
		for(;p&&!trans[p][c];p=fa[p]) trans[p][c]=np;
		if(!p) fa[np]=1;
		else{
			int q=trans[p][c];
			if(lth[q]==lth[p]+1) fa[np]=q;
			else{
				int nq=++cnt;lth[nq]=lth[p]+1;
				mcy(trans[nq],trans[q]);
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				for(;p&&trans[p][c]==q;p=fa[p]) trans[p][c]=nq;
			}
		}
	}
	void build(char str[]){
		int len=strlen(str);
		for(int i=0;i<len;i++) extend(str[i]-'a');
	}
}sam;
int n,rank[MAXN];
char c[MAXN];
bool cmp(int i,int j){
	return sam.lth[i]>sam.lth[j];
}
void init(){
	n=strlen(c);
	sam.build(c);
	for(int i=1;i<=sam.cnt;i++) rank[i]=i;
	sort(rank+1,rank+sam.cnt+1,cmp);
	for(int i=1;i<=sam.cnt;i++){//现在我来更新一下s 
		int in=rank[i];
		sam.s[in]=1;
		for(int j=0;j<26;j++) if(sam.trans[in][j]) sam.s[in]+=sam.s[sam.trans[in][j]];
	}
	int p=1;
	for(int i=0;i<n;i++){
		p=sam.trans[p][c[i]-'a'];
		sam.r[p]++;
	}
	for(int i=1;i<=sam.cnt;i++){
		int in=rank[i];
		if(!sam.fa[in]) continue;
		sam.r[sam.fa[in]]+=sam.r[in];//r就是每个串出现多少次 
	}
	sam.r[1]=0;
	for(int i=1;i<=sam.cnt;i++){
		int in=rank[i];
		sam.siz[in]=sam.r[in];
		for(int j=0;j<26;j++) if(sam.trans[in][j]) sam.siz[in]+=sam.siz[sam.trans[in][j]];
	}
}
void solve1(int pz){
	int p=1,k=pz;
    while(k){
    	for(int i=0;i<26;i++){
            if(!sam.trans[p][i]) continue;
            if(k<=sam.s[sam.trans[p][i]]){
                --k;p=sam.trans[p][i];
                cout<<char('a'+i);
                break;
            }
            else k-=sam.s[sam.trans[p][i]];
        }
    }
    printf("\n");
}
void solve2(int pz){
	int p=1,k=pz;
    while(k){
        for(int i=0;i<26;i++){
            if(!sam.trans[p][i]) continue;
            if(k<=sam.siz[sam.trans[p][i]]){
                k-=sam.r[sam.trans[p][i]];p=sam.trans[p][i];
                cout<<char('a'+i);
                break;
            }
            else k-=sam.siz[sam.trans[p][i]];
        }
    }
    printf("\n");
}

void input(){
	scanf("%s",c);
	init();
}
void xxj(){
	int k,typ;
	scanf("%d%d",&typ, &k);
	if(typ==0) solve1(k);
	else solve2(k);
}
void testout(){
	for(int i=1;i<=sam.cnt;i++) cout<<sam.siz[i]<<' ';
	cout<<endl;
}
int main(){
	input();
	xxj();
	//testout();
	return 0;
}