福州市城乡建设网站张麒蛰,上海app开发费用,网易163企业邮箱格式,在线音乐网站开发正题 大意
一个字符串#xff0c;要求第k小的子串。 解题思路
先建立一个后缀自动机#xff0c;然后用一个numinum_inumi表示第iii个节点的可以到达的点所表示的子串总和#xff0c;然后从第1号点开始查找#xff0c;判断一下找到第k小所在的节点后#xff0c;然后查找…正题 大意
一个字符串要求第k小的子串。 解题思路
先建立一个后缀自动机然后用一个numinum_inumi表示第iii个节点的可以到达的点所表示的子串总和然后从第1号点开始查找判断一下找到第k小所在的节点后然后查找输出。 代码
#includecstdio
#includealgorithm
#includecstring
#define N 200010
#define Get(W) Wa?W-71:W-A
#define fuGet(W) W26?W71:WA
using namespace std;
int l,last,fail[N],next[N][56],tot,len[N],num[N];
int ls[N],v[N],head,tail,q[N];
long long sum;
char s[100001];
int New(int x,int y){next[x][y]tot;len[tot]len[x]1;
}
void bfs()
{head0;q[1]1;tail1;v[1]1;do{int xq[head];for (int i0;i52;i)if (next[x][i]!v[next[x][i]]){v[next[x][i]]1;q[tail]next[x][i];//建立顺序}}while (headtail);for (;tail;tail--){int xq[tail];for (int i0;i52;i)if (next[x][i]){ls[x]i;num[x]num[next[x][i]]1;//按顺序计算答案}}
}
void Get_answer()
{int x1;while (sum){if (!ls[x]!next[x][0])break;for (int i0;ils[x];i)if (next[x][i]){if (num[next[x][i]]1sum||ils[x])//在当前节点的搜索树中{printf(%c,fuGet(i));int ynext[x][i];sum--;if (sum) xy;//进入该节点break;}else sum-num[next[x][i]]1;//跳转下一棵}}
}
int main()
{scanf(%s,s);scanf(%lld,sum);lstrlen(s);last1;len[1]0;fail[1]0;tot1;for (int i0;il;i){int addcGet(s[i]);int klast,j0;New(last,addc);//新建节点lasttot;for (jfail[k];j;jfail[j])if (!next[j][addc])next[j][addc]last;//直接连接else{int znext[j][addc];if (len[z]len[j]1)fail[last]z;//连接else{New(j,addc);for (int l0;l52;l)next[tot][l]next[z][l];//继承指针fail[tot]fail[z];fail[z]fail[last]tot;//继承for (int lj;l;lfail[l])if (next[l][addc]z) next[l][addc]tot;//继承连接}break;}if (!j) fail[last]1;/特判}bfs();//计算numGet_answer();
}
