【[TJOI2015]弦论】

\(SA+SAM\)

第一问显然是一个\(SAM\)的经典问题，我们排完序之后直接使用一直往下找\(n+1-sa[i]-het[i]\)就好了，找到\(K\)减不动了输出就好了

第二问是\(SAM\)的经典问题，我们在\(SAM\)上求出子树和跑一遍\(dfs\)就好了，每层都贪心的减\(K\)，减不动就停下来好了

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define re register

#define LL long long

#define maxn 500005

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

int opt,K;

char S[maxn];

int n,m;

namespace SA

{

	int tp[maxn],sa[maxn],rk[maxn],tax[maxn],het[maxn];

	inline void qsort()

	{

    	for(re int i=0;i<=m;i++) tax[i]=0;

    	for(re int i=1;i<=n;i++) tax[rk[i]]++;

    	for(re int i=1;i<=m;i++) tax[i]+=tax[i-1];

    	for(re int i=n;i;--i) sa[tax[rk[tp[i]]]--]=tp[i];

	}

    inline void work()

    {

    	for(re int i=1;i<=n;i++) rk[i]=S[i],tp[i]=i;

    	m=255;qsort();

    	for(re int w=1,p=0;p<n;w<<=1,m=p)

    	{

        	p=0;

        	for(re int i=1;i<=w;i++) tp[++p]=n-w+i;

        	for(re int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;

        	qsort();

        	for(re int i=1;i<=n;i++) std::swap(rk[i],tp[i]);

       	 	rk[sa[1]]=p=1;

        	for(re int i=2;i<=n;i++) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;

    	}

    	int k=0;

    	for(re int i=1;i<=n;i++)

    	{

        	if(k) --k;

        	int j=sa[rk[i]-1];

        	while(S[i+k]==S[j+k]) ++k;

        	het[rk[i]]=k;

    	}

        for(re int i=1;i<=n;i++)

        if(K>(n+1-sa[i]-het[i])) K-=n+1-sa[i]-het[i];

        else

        {

            for(re int j=sa[i];j<=sa[i]+het[i]+K-1;j++)

                putchar(S[j]);

            return;

        }

        puts("-1");

    }

}

namespace SAM

{

	int link[maxn<<1],son[maxn<<1][26],sz[maxn<<1],len[maxn<<1];

	int tax[maxn<<1],a[maxn<<1],sum[maxn<<1];

	int lst=1,cnt=1;

	inline void ins(int c)

	{

		int f=lst,p=++cnt; lst=p;

		len[p]=len[f]+1,sz[p]=1;

		while(f&&!son[f][c]) son[f][c]=p,f=link[f];

		if(!f) {link[p]=1;return;}

		int x=son[f][c];

		if(len[f]+1==len[x]) {link[p]=x;return;}

		int y=++cnt;

		len[y]=len[f]+1,link[y]=link[x],link[x]=link[p]=y;

		for(re int i=0;i<26;i++) son[y][i]=son[x][i];

		while(f&&son[f][c]==x) son[f][c]=y,f=link[f];

	}

	inline void work()

	{

		for(re int i=1;i<=n;i++) ins(S[i]-'a');

		for(re int i=1;i<=cnt;i++) tax[len[i]]++;

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

		for(re int i=1;i<=cnt;i++) a[tax[len[i]]--]=i;

		for(re int i=cnt;i;--i) sz[link[a[i]]]+=sz[a[i]]; sz[1]=0;

		for(re int i=cnt;i;--i) sum[a[i]]+=sz[a[i]];

		for(re int i=cnt;i;--i) for(re int j=0;j<26;j++) if(son[a[i]][j]) sum[a[i]]+=sum[son[a[i]][j]];

		if(K>sum[1]) {puts("-1");return;}

		int now=1;K-=sz[now];

		while(K>0)

		{

			int i=0;

			while(K>sum[son[now][i]]) {K-=sum[son[now][i]];i++;}

			now=son[now][i];

			putchar('a'+i),K-=sz[now];

		}

	}

}

int main()

{

    scanf("%s",S+1);n=strlen(S+1);scanf("%d%d",&opt,&K);

    if(!opt) SA::work();

        else SAM::work();

    return 0;

}

巴特西

【[TJOI2015]弦论】

最新文章

热门文章