求 kth 子串。支持區分可重複子串和不可重複子串。

const int N = int(1e6) + 9, Z = 26; namespace SAM{ int trans[N][Z],par[N],len[N],sum[N],cnt[N],tail,tot; char buf[N]; int new_node(){ RST(trans[tot]); return tot++; } int new_node(int u){ CPY(trans[tot],trans[u]),par[tot]=par[u]; return tot++; } #define v trans[u] #define p par[u] #define pp par[uu] int Ext(int c){ int u = tail, uu = new_node(); len[uu] = len[u] + 1; while (u && !v) v = uu, u = p; if (!u && !v) v = uu, pp = 0; else{ if (len[v] == len[u] + 1) pp = v; else{ int _v = v, vv = new_node(_v); len[vv] = len[u] + 1; par[_v] = pp = vv; while (v == _v) v = vv, u = p; } } return tail = uu; } int adj[N][26]; void Init(){ tail = tot = 0; new_node(), RS(buf); REP_S(cur, buf) cnt[Ext(*cur - 'a')] = 1; static int C[N], Q[N]; REP(i, tot) ++C[len[i]]; REP_1(i, len[tail]) C[i] += C[i-1]; REP(i, tot) Q[--C[len[i]]] = i; //FOR(u, 1, tot) { DWN(i, tot, 1) { int u = Q[i]; if (p) cnt[p] += cnt[u]; //cout << u << " " << cnt[u] << endl; } int t; RD(t); DWN(i, tot, 0){ int u = Q[i]; if (t == 0) cnt[u] = 1; int t = 0; sum[u] = cnt[u]; REP(c, Z) if (v){ adj[u][t++] = c; sum[u] += sum[v]; } } DWN(u, tot, 0){ //cnt[p] += cnt[u]; // cout << u << " " << sum[u] << " " << cnt[u] << endl; } cnt[0] = 0; } #undef c #define c adj[u][i] void kth(int k){ --k; if (k >= sum[0]) { cout << -1 << endl; return; } int u = 0; while (k >= cnt[u]){ k -= cnt[u]; for (int i=0;;++i){ if (k >= sum[v]) k -= sum[v]; else{ putchar(c+'a'); u = v; break; } } } puts(""); } } using namespace SAM; int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif Init(); //Rush kth(RD()); kth(RD()); }