网站开发职位工资,上海网站建设赢昶,大型的网站开发,网站怎么做域名实名认证吗正题
题目链接:https://www.luogu.com.cn/problem/P3975 题目大意
给一个字符串sss和t,kt,kt,k。求字符串sss第kkk大的子串。
当T0T0T0时#xff0c;相同的子串算一个当T1T1T1时#xff0c;不同位置的相同子串算不同的串 解题思路
当T0T0T0时很简单#xff0c;对于每个位…正题
题目链接:https://www.luogu.com.cn/problem/P3975 题目大意
给一个字符串sss和t,kt,kt,k。求字符串sss第kkk大的子串。
当T0T0T0时相同的子串算一个当T1T1T1时不同位置的相同子串算不同的串 解题思路
当T0T0T0时很简单对于每个位置求该位置开始能到多少个串即可也就是fx∑x−y(fy1)f_x\sum_{x-y}(f_y1)fxx−y∑(fy1)然后根据fxf_xfx像权值线段树那样走就好了
当T1T1T1时我们需要求出每个endposendposendpos的大小因为对于走到该节点的一个子串显然在该位置的endposendposendpos的集合为结尾也有一个一样的子串因为每个endposendposendpos包含所有的子节点的endposendposendpos所以我们对于一个原串的后缀让siz1siz1siz1之后让每个节点加上它parentsparentsparents树上节点的sizsizsiz就好。
用桶排就可以做到O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e61;
int n,las,cnt,k,t,c[N],fa[N],sum[N];
int siz[N],ch[N][26],a[N],len[N];
char s[N];
void add(int c){int plas;int nplascnt;len[np]len[p]1;siz[cnt];for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{int qch[p][c];if(len[p]1len[q])fa[np]q;else{int nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[np]fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return;
}
void solve(int x,int k){if(ksiz[x])return;k-siz[x];for(int i0;i26;i){if(!ch[x][i])continue;if(ksum[ch[x][i]])k-sum[ch[x][i]];else {printf(%c,ia);solve(ch[x][i],k);return;}}return;
}
int main()
{cntlas1;scanf(%s,s1);nstrlen(s1);for(int i1;in;i)add(s[i]-a);scanf(%d%d,t,k);for(int i1;icnt;i)c[len[i]];for(int i1;in;i)c[i]c[i-1];for(int i1;icnt;i)a[c[len[i]]--]i;for(int icnt;i1;i--)siz[fa[a[i]]]siz[a[i]];for(int i1;icnt;i)t?(sum[i]siz[i]):(sum[i]siz[i]1);siz[1]siz[0]sum[1]sum[0]0;for(int icnt;i1;i--)for(int j0;j26;j)if(ch[a[i]][j])sum[a[i]]sum[ch[a[i]][j]]; if(sum[1]k)printf(-1);else solve(1,k);return 0;
}
