bzoj3998 [TJOI2015]弦论

bzoj3998 [TJOI2015]弦论

​​ 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 Source 求字典序第k小的子串 那么建SAM 然后拓扑排序 枚举出 每个节点管辖的范围内有多少个子串 然后类似二分的往下去查找即可 因为这样的话就是按照字典序走下去的

#include#include#include#define N 1000010using namespace std;int size[N],fa[N],len[N],ch[N][26],last=1,cnt=1,root=1;char s[N>>1];int T,k,c[N>>1],rk[N],sum[N];inline void insert1(int x){ int np=++cnt,p=last;len[np]=len[p]+1;fa[np]=p; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p) fa[np]=root;else{int q=ch[p][x]; if(len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];fa[np]=fa[q]=nq; len[nq]=len[p]+1;for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;size[np]=1;}inline void dfs(int x){ if (k<=size[x]) return;k-=size[x]; for (int i=0;i<26;++i) if (ch[x][i]){ if (k<=sum[ch[x][i]]) {putchar('a'+i),dfs(ch[x][i]);return;} k-=sum[ch[x][i]]; }}int main(){// freopen("bzoj3998.in","r",stdin); scanf("%s",s);int le=strlen(s); for (int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。