驻马店做网站,网站建设需要包含什么,帝国cms响应式网站模板,有哪些公司的网站做的很好看题目链接 \(Click\) \(Here\) 题目大意#xff1a; 重复子串不算的第\(k\)大子串重复子串计入的第\(k\)大子串写法#xff1a;后缀自动机。 和\(OI\) \(Wiki\)上介绍的写法不太一样#xff0c;因为要同时解决两个问题。 把字符串每个前缀所在等价类的\(siz\)记为\(1\)#…题目链接 \(Click\) \(Here\) 题目大意 重复子串不算的第\(k\)大子串重复子串计入的第\(k\)大子串写法后缀自动机。 和\(OI\) \(Wiki\)上介绍的写法不太一样因为要同时解决两个问题。 把字符串每个前缀所在等价类的\(siz\)记为\(1\)然后在\(parent\) \(tree\)上跑一次统计就可以求出来每一个等价类在串中出现的次数。这里采用类似后缀排序的方法对字符串按\(len\)为关键字进行排序。至于经过每个点的路径数\(sum\)可以在\(Trie\)边上对后面节点的\(sum\)每一个等价类在串中出现次数求和得到初始值等于\(siz\)因为每个点还有不选的情况。 不要忘了把\(siz[1]\)和\(sum[1]\)清空 #include bits/stdc.h
using namespace std;const int N 1100010;char s[N];
int las 1, node 1;
int fa[N], len[N], siz[N], ch[N][26];void extend (int c) {register int p, q, x, y;p las, q node; las q;len[q] len[p] 1; siz[q] 1;while (p ! 0 ch[p][c] 0) {ch[p][c] q;p fa[p];}if (p 0) {fa[q] 1;} else {x ch[p][c];if (len[x] len[p] 1) {fa[q] x;} else {y node;fa[y] fa[x];fa[x] fa[q] y;len[y] len[p] 1;memcpy (ch[y], ch[x], sizeof (ch[x]));while (p ! 0 ch[p][c] x) {ch[p][c] y;p fa[p];}}}
}int t, k, nd[N], bin[N]; long long sum[N];void output (int u) {if (k siz[u]) return;k - siz[u];register int i;for (i 0; i 26; i) {if (ch[u][i]) {if (k sum[ch[u][i]]) {k - sum[ch[u][i]];} else {printf (%c, i a);output (ch[u][i]);return;}}}
}int main () {scanf (%s %d %d, s, t, k);register int i, j, n;n strlen (s);for (i 0; i n; i) extend (s[i] - a);for (i 1; i node; i) bin[len[i]];for (i 1; i node; i) bin[i] bin[i - 1];for (i 1; i node; i) nd[bin[len[i]]--] i;for (i node; i 1; --i) siz[fa[nd[i]]] siz[nd[i]];for (i 1; i node; i) t 0 ? (sum[i] siz[i] 1) : (sum[i] siz[i]);siz[1] sum[1] 0;for (i node; i 1; --i) {for (j 0; j 26; j) {if (ch[nd[i]][j]) {sum[nd[i]] sum[ch[nd[i]][j]];}}}if (sum[1] k) {puts (-1);} else {output (1);}
}\(p.s\)关于后缀数组求第一问的方法 枚举每一个后缀第i个后缀对答案的贡献为\(len−sa[i]1−height[i]\)。 转载于:https://www.cnblogs.com/maomao9173/p/10452644.html
