题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3998
题意：对于一个给定长度为 N 的字符串，求它的第 K 小子串是什么。
本质相同与否的子串算不算一个其实只影响了 SAM 上 right 集合大小的含义。
直接建 SAM，拓扑 DP 一下，从根开始贪心的 dfs 即可。
发现拓扑序即按照 mx 排序，可以大幅优化常数。一号板子题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 500010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char s[N]; int T,k; namespace SAM { #define MAXN 1000010 int ch[MAXN][26],fail[MAXN]; int mx[MAXN],val[MAXN],sum[MAXN];//val right大小 int last=1,tot=1,rt=1; int ord[MAXN],bin[MAXN]; void add(int x) { int p=last,np=++tot,q,nq; last=np,mx[np]=mx[p]+1,val[np]=1; while(p&&!ch[p][x])ch[p][x]=np,p=fail[p]; if(p==0){fail[np]=rt;return ;} q=ch[p][x]; if(mx[q]==mx[p]+1){fail[np]=q;return ;} nq=++tot,mx[nq]=mx[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fail[nq]=fail[q],fail[np]=fail[q]=nq; while(p&&ch[p][x]==q)ch[p][x]=nq,p=fail[p]; } void count() { for(int i=1;i<=tot;i++)bin[mx[i]]++; for(int i=1;i<=tot;i++)bin[i]+=bin[i-1]; for(int i=tot;i;i--)ord[bin[mx[i]]--]=i; for(int i=tot;i;i--) { int x=ord[i]; if(T)val[fail[x]]+=val[x]; else val[x]=1; } val[1]=0; for(int i=tot;i;i--) { int x=ord[i]; sum[x]=val[x]; for(int j=0;j<26;j++) sum[x]+=sum[ch[x][j]]; } } void dfs(int x,int k) { if(k<=val[x])return ; k-=val[x]; for(int i=0;i<26;i++) if(ch[x][i]) { int to=ch[x][i]; if(k<=sum[to]) { putchar(i+'a'); dfs(to,k); return ; } k-=sum[to]; } } } int main() { scanf("%s",s+1); int n=strlen(s+1); for(int i=1;i<=n;i++) SAM::add(s[i]-'a'); T=read(),k=read(); SAM::count(); if(k>SAM::sum[1])puts("-1"); else SAM::dfs(1,k); } |
Comments | NOTHING