[BZOJ3998][TJOI2015]弦論

試題描述

對于一個給定長度為N的字符串，求它的第K小子串是什么。

輸入

第一行是一個僅由小寫英文字母構成的字符串S

第二行為兩個整數T和K，T為0則表示不同位置的相同子串算作一個。T=1則表示不同位置的相同子串算作多個。K的意義如題所述

輸出

輸出僅一行，為一個數字串，為第K小的子串。如果子串數目不足K個，則輸出-1

輸入示例

aabc 0 3

輸出示例

aab

數據規模及約定

N<=5*10^5

T<2

K<=10^9

題解

對于 T = 0 的情況，就是這道題；對于 T = 1 的情況就是把每個節點的權值由 1 變成 right 集合的大小。

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std;int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }return x * f; }#define maxn 1000010 #define maxa 26char S[maxn]; int len, T, K;int rt, last, ToT, to[maxn][maxa], par[maxn], Max[maxn], val[maxn], f[maxn]; void extend(int x) {int p = last, np = ++ToT; Max[np] = Max[p] + 1; val[np] = 1; last = np;while(p && !to[p][x]) to[p][x] = np, p = par[p];if(!p){ par[np] = rt; return ; }int q = to[p][x];if(Max[q] == Max[p] + 1){ par[np] = q; return ; }int nq = ++ToT; Max[nq] = Max[p] + 1; if(!T) val[nq] = 1;memcpy(to[nq], to[q], sizeof(to[q]));par[nq] = par[q];par[q] = par[np] = nq;while(p && to[p][x] == q) to[p][x] = nq, p = par[p];return ; }int sa[maxn], Ws[maxn];int main() {scanf("%s", S); T = read(); K = read();len = strlen(S);rt = last = ToT = 1;for(int i = 0; i < len; i++) extend(S[i] - 'a');for(int i = 1; i <= ToT; i++) Ws[len-Max[i]]++;for(int i = 1; i <= len; i++) Ws[i] += Ws[i-1];for(int i = ToT; i; i--) sa[Ws[len-Max[i]]--] = i;if(T)for(int i = 1; i <= ToT; i++) {int u = sa[i];if(par[u] != rt) val[par[u]] += val[u];}for(int i = 1; i <= ToT; i++) {int u = sa[i];f[u] = val[u];for(int c = 0; c < maxa; c++) f[u] += f[to[u][c]];}if(K > f[1]) return puts("-1"), 0;int p = rt;while(K > 0) {for(int c = 0; c < maxa; c++) if(K > f[to[p][c]])K -= f[to[p][c]];else {putchar(c + 'a');K -= val[p = to[p][c]];break;}}putchar('\n');return 0; }

?

轉載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/6554200.html

總結

以上是生活随笔為你收集整理的[BZOJ3998][TJOI2015]弦论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。