首页 > 代码库 > 【BZOJ-3998】弦论 后缀自动机
【BZOJ-3998】弦论 后缀自动机
3998: [TJOI2015]弦论
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 2018 Solved: 662
[Submit][Status][Discuss]
Description
对于一个给定长度为N的字符串,求它的第K小子串是什么。
Input
第一行是一个仅由小写英文字母构成的字符串S
第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
Output
输出仅一行,为一个数字串,为第K小的子串。如果子串数目不足K个,则输出-1
Sample Input
aabc
0 3
0 3
Sample Output
aab
HINT
N<=5*10^5
T<2
K<=10^9
Source
Solution
后缀自动机的裸题?不过给我挺大帮助的。
建出后缀自动机求K大的问题,先拓扑排序/基数排序,然后递推出每个节点能到的子串数,然后dfs一遍加加减减。
这个题在递推的时候讨论一下即可,T=0时说明每个状态代表一个子串(除空串以外),T=1时每个节点的Parent树的子树中的节点数都是可以得到的子串数,所以需要累加。
而这个累加的过程,可以理解成是求出$Right$集合的大小,所以构建时的新建节点显然不能重复计算。
然后dfs一遍,类似于线段树上二分的思想,输出答案。
自己没有写递归的写法,直接用的while里非递归。
Code
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define MAXN 500010char A[MAXN],ans[MAXN];int N,T,K;namespace SAM{ int son[MAXN<<1][27],par[MAXN<<1],len[MAXN<<1],root,last,sz,size[MAXN<<1]; inline void Init() {root=sz=last=1;} inline void Extend(int c) { int cur=++sz,p=last; len[cur]=len[p]+1; size[cur]=1; while (p && !son[p][c]) son[p][c]=cur,p=par[p]; if (!p) par[cur]=root; else { int q=son[p][c]; if (len[p]+1==len[q]) par[cur]=q; else { int nq=++sz; memcpy(son[nq],son[q],sizeof(son[nq])); len[nq]=len[p]+1; par[nq]=par[q]; while (p && son[p][c]==q) son[p][c]=nq,p=par[p]; par[cur]=par[q]=nq; } } last=cur; } inline void Build() {Init(); for (int i=1; i<=N; i++) Extend(A[i]-‘a‘+1);} int st[MAXN],id[MAXN<<1],sum[MAXN<<1]; inline void Pre() { for (int i=1; i<=sz; i++) st[len[i]]++; for (int i=1; i<=N; i++) st[i]+=st[i-1]; for (int i=1; i<=sz; i++) id[st[len[i]]--]=i; if (!T) { for (int i=sz; i>=1; i--) size[i]=1; size[root]=0; for (int i=sz,Sum=0; i>=1; i--,Sum=0) { for (int j=1; j<=26; j++) Sum+=sum[son[id[i]][j]]; sum[id[i]]=Sum+1; } } else { for (int i=sz; i>=1; i--) size[par[id[i]]]+=size[id[i]]; size[root]=0; for (int i=sz; i>=1; i--) { sum[id[i]]=size[id[i]]; for (int j=1; j<=26; j++) sum[id[i]]+=sum[son[id[i]][j]]; } } } inline void Query(int K) { int now=root,tot=0; while (K) { for (int i=1; i<=26; i++) if (son[now][i]) if (sum[son[now][i]]>=K) { ans[++tot]=‘a‘+i-1; K-=size[son[now][i]]; now=son[now][i]; break; } else K-=sum[son[now][i]]; } ans[++tot]=0; }}using namespace SAM;int main(){ scanf("%s",A+1); N=strlen(A+1); SAM::Build(); scanf("%d%d",&T,&K); SAM::Pre(); if (sum[root]<K) puts("-1"); else Query(K),puts(ans+1); return 0;}
【BZOJ-3998】弦论 后缀自动机
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。