willy108

Substring Order 2

Sep 16th, 2021
935
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. char str[MX];
  3. int sa[MX], rk[MX], buckets[MX], lcp[MX], gl2[MX]; //using buckets for readability
  4. int tmp[MX], pos[MX], st[MX * 2][18], n;
  5. ll k, tot = 0;
  6. void comp_SA(){
  7.   int mx = 260;
  8.   for(int i = 1; i<=n; i++){
  9.     sa[i] = i;
  10.     rk[i] = str[i];
  11.   }
  12.  
  13.   for(int i = 1; i >> 1 < n; i <<= 1){
  14.     int k = i >> 1, p = k;
  15.     for(int j = 1; j<=k; j++) buckets[j] = n - (j - 1);
  16.     for(int j = 1; j<=n; j++) if(sa[j] > k) buckets[++p] = sa[j] - k;
  17.     for(int j = 1; j<=n; j++) pos[j] = 0;
  18.     for(int j = 1; j<=n; j++) pos[rk[j]]++;
  19.     for(int j = 1; j<=mx; j++) pos[j] += pos[j - 1];
  20.     for(int j = n; j; j--) sa[pos[rk[buckets[j]]]--] = buckets[j];
  21.     for(int j = 1; j<=n; j++) tmp[sa[j]] = tmp[sa[j - 1]] + (rk[sa[j]] != rk[sa[j - 1]] || rk[sa[j] + k] != rk[sa[j - 1] + k]);
  22.     for(int j = 1; j<=n; j++) rk[j] = tmp[j];
  23.     mx = rk[sa[n]];
  24.     if(mx == n) break;
  25.   }
  26.    
  27. }
  28.  
  29. void make_lcp(){
  30.   for(int i = 1; i<=n; i++){
  31.         if(rk[i] == 1) cont;
  32.     lcp[rk[i]] = max(0, lcp[rk[i - 1]] - 1);
  33.     for(; str[i + lcp[rk[i]]] == str[sa[rk[i] - 1] + lcp[rk[i]]]; lcp[rk[i]]++);
  34.   }
  35. }
  36.  
  37. void rmq_precomp(){
  38.   init(st, 63);
  39.     gl2[1] = 0;
  40.     for(int i = 2; i<=n; i++) gl2[i] = 1 + gl2[i/2];
  41.   for(int i = 1; i<=n; i++) st[i][0] = lcp[i];
  42.   for(int j = 1; (1 << j) <= n; j++){
  43.     for(int i = 1; i <= n; i++){
  44.       st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  45.     }
  46.   }
  47. }
  48.  
  49. int query(int a, int b){ //max prefix amoung suffix starting at a and suffix starting at b [a, b]
  50.     //return 0;
  51.     a++, b++;
  52.   if(a > b) swap(a, b);
  53.   int k = gl2[b - a];
  54.   return min(st[a][k], st[b - (1 << k)][k]);
  55. }
  56. bool add(ll val){
  57.     if(tot + val >= k) return 1;
  58.     tot += val;
  59.     return 0;
  60. }
  61.  
  62. bool check(int x, int k, int pre){
  63.     return query(k, x) >= pre;
  64. }
  65.  
  66. int bsrch(int l, int r, int k, int pre){
  67.     if(r - l < 2){
  68.         for(int i = l; i <= r; i++){
  69.             if(!check(i, k, pre)) return i - 1;
  70.         }
  71.         return r;
  72.     }
  73.     int mid = (l + r)/2;
  74.     if(check(mid, k, pre)){
  75.         return bsrch(mid, r, k, pre);
  76.     }else{
  77.         return bsrch(l, mid-1, k, pre);
  78.     }
  79. }
  80. void print(int l, int r){
  81.     for(int i = l; i<=r; i++) cout << str[i];
  82.     cout << "\n";
  83. }
  84. int main(){
  85.   cin.tie(0) -> sync_with_stdio(0);
  86.     cin >> (str + 1);
  87.     cin >> k;
  88.     n =strlen(str + 1);
  89.     comp_SA();
  90.     make_lcp();
  91.     rmq_precomp();
  92.     int p = 0;
  93.     for(int i = 1; i<=n; i++){
  94.         int old = p;
  95.         for(p = max(p, lcp[i] + 1); p <= lcp[i+1]; p++){
  96.             int v = bsrch(i+1, n, i, p) - i+1;
  97.             if(add(v)){
  98.                 print(sa[i], sa[i] + p - 1);
  99.                 i = n+1; break;
  100.             }
  101.         }
  102.         if(i > n) break;
  103.         p = lcp[i+1];
  104.         int dist = (n - (sa[i] + max(old, p))) + 1;
  105.         if(add(dist)){
  106.             print(sa[i], sa[i] + max(old, p) + k - tot - 1);
  107.             break;
  108.         }
  109.     }
  110.   return 0;
  111. }
  112.  
RAW Paste Data