注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3998][TJOI2015]弦论  

2015-04-22 20:26:44|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3998: [TJOI2015]弦论

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 128  Solved: 42
[Submit][Status][Discuss]

Description

对于一个给定长度为N的字符串,求它的第K小子串是什么。

Input

 第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

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

Sample Input

aabc 0 3

Sample Output

aab

HINT

 N<=5*10^5

T<2

K<=10^9

Solution

后缀自动机
对于每个节点维护val
T=0的时候,val=1
T=1的时候,每插入一个结点,沿当前插入的主串上的节点的fail一直往上跳到S,路径上的fail++
然后维护f,f[i]=val[i]+Σf[son]
意思是说 走到这个节点 再往下走 还能走到 多少个 以 当前节点到根的路径为开头 的子串 的个数
于是就可以在sam上面“二分"?反正跟线段树上二分差不多

Code

黄学长问我 1k代码是后缀自动机吗?
当然是啦= =
/**************************************************************
    Problem: 3998
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:5252 ms
    Memory:133924 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 1<<20
int n,T,k,tot=1,S=1,las=1,fail[N],ch[N][26],val[N],f[N],len[N],id[N],c[N],i,j,l;
char s[N],op[N],*O=op;
void add(char c){
    int p=las,np=++tot;
    for(val[np]=1,len[np]=len[p]+1;p&&!ch[p][c];p=fail[p])ch[p][c]=np;
    if(las=np,!p)fail[np]=S;
    else if(len[p]+1==len[ch[p][c]])fail[np]=ch[p][c];
    else{
        int q=ch[p][c],r=++tot;len[r]=len[p]+1;if(!T)val[r]=1;
        fail[r]=fail[q],memcpy(ch[r],ch[q],sizeof(ch[q]));
        for(fail[np]=fail[q]=r;p&&ch[p][c]==q;p=fail[p])ch[p][c]=r;
    }
}
int main(){
    scanf("%s",s+1);scanf("%d%d",&T,&k);
    for(n=1;s[n];n++)add(s[n]-'a');n--;
    for(i=1;i<=tot;i++)c[len[i]]++;
    for(i=1;i<=n;i++)c[i]+=c[i-1];
    for(i=tot;i;i--)id[c[len[i]]--]=i;
    if(T)for(j=tot;j;j--)i=id[j],val[fail[i]]+=val[i];
    for(val[1]=0,j=tot;j;j--)
    for(i=id[j],f[i]=val[i],l=0;l<26;l++)f[i]+=f[ch[i][l]];
    if(f[1]<k)return puts("-1"),0;
    for(i=S;k>val[i];){
        for(k-=val[i],j=0;j<26;j++)
        if(f[ch[i][j]]<k)k-=f[ch[i][j]];
        else{*O++=j+'a';i=ch[i][j];break;}
    }
    puts(op);
}

  评论这张
 
阅读(372)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018