「BZOJ3998」[TJOI2015] 弦论
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
题解
日常orz PoPoQQQ大爷的时候发现了这道裸题。。。
建出自动机求K大。。。没了。。。
T=0 除了根以外的状态都代表1个串
T=1 每个状态fail子树结束结点个数即为串的个数
大爷说卡常数。？好像没发现。。。
要是比赛看到这种题不是爽的飞起。。。
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; int T,n,K; char ch[500005]; struct sam{ int last,cnt; int a[1000005][26],fa[1000005],mx[1000005],val[1000005],sum[1000005]; int v[500005],q[1000005]; sam(){ last=++cnt; } void extend(int c){ int p=last,np=last=++cnt; mx[np]=mx[p]+1;val[np]=1; while(!a[p][c]&&p)a[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else { int q=a[p][c]; if(mx[p]+1==mx[q])fa[np]=q; else { int nq=++cnt;mx[nq]=mx[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=fa[p]; } } } void pre(){ for(int i=1;i<=cnt;i++)v[mx[i]]++; for(int i=1;i<=n;i++)v[i]+=v[i-1]; for(int i=cnt;i;i--)q[v[mx[i]]--]=i; for(int i=cnt;i;i--) { int t=q[i]; if(T==1)val[fa[t]]+=val[t]; else val[t]=1; } val[1]=0; for(int i=cnt;i;i--) { int t=q[i];sum[t]=val[t]; for(int j=0;j<26;j++) sum[t]+=sum[a[t][j]]; } } void dfs(int x,int K){ if(K<=val[x])return; K-=val[x]; for(int i=0;i<26;i++) if(int t=a[x][i]) { if(K<=sum[t]) { putchar(i+'a'); dfs(t,K); return; } K-=sum[t]; } } }sam; int main() { scanf("%s",ch+1); n=strlen(ch+1); scanf("%d%d",&T,&K); for(int i=1;i<=n;i++) sam.extend(ch[i]-'a'); sam.pre(); if(K>sam.sum[1])puts("-1"); else sam.dfs(1,K); return 0; } |
计数器 9790091
OI 课件=>
OI 课件=>
扑通扑通跪下来，千古神犇黄哲威
原来对mx[]排序后可以得到自动机和后缀树的拓扑序。怪不得没被卡常数。
扑通扑通跪下来，千古神犇黄哲威
扑通扑通跪下来，千古神犇黄哲威
黄学长，求问这个题T=1情况怎么用后缀数组做>_<
求一下每个串是往后多少个串的前缀，这个可以在单调栈上二分，然后应该会做了吧