willy108

Substring Order 1

Sep 16th, 2021
968
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];
  4. int tmp[MX], pos[MX], st[MX * 2][40], n;
  5.  
  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. int main(){
  38.   cin.tie(0) -> sync_with_stdio(0);
  39.     cin >> (str + 1);
  40.     n = strlen(str + 1);
  41.     ll k; cin >> k;
  42.     comp_SA();
  43.     make_lcp();
  44.     for(int i = 1; i<=n; i++){
  45.         int dist = (n - (sa[i] + lcp[i])) + 1;
  46.         if(dist < k){
  47.             k -= dist;
  48.         }else{
  49.             for(int j = sa[i]; j < sa[i] + lcp[i] + k; j++){
  50.                 cout << str[j];
  51.             }
  52.             cout << "\n";
  53.             break;
  54.         }
  55.     }
  56.   return 0;
  57. }
  58.  
RAW Paste Data