willy108

Substring Distribution

Sep 16th, 2021
1,033
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int max_v = 1e5 +10, LOGN = 40;
  2. char str[max_v];
  3. int sa[max_v], rk[max_v], buckets[max_v], lcp[max_v];
  4. int tmp[max_v], pos[max_v], st[max_v * 2][LOGN], n;
  5. ll psum[MX];
  6. void print_arr(int n, int * arr){
  7.   for(int i = 1; i<=n; i++) printf("%d ", arr[i]);
  8.   puts("");
  9. }
  10.  
  11. void comp_SA(){
  12.   int mx = 260;
  13.   for(int i = 1; i<=n; i++){
  14.     sa[i] = i;
  15.     rk[i] = str[i];
  16.   }
  17.  
  18.   for(int i = 1; i >> 1 < n; i <<= 1){
  19.     int k = i >> 1, p = k;
  20.     for(int j = 1; j<=k; j++) buckets[j] = n - (j - 1);
  21.     for(int j = 1; j<=n; j++) if(sa[j] > k) buckets[++p] = sa[j] - k;
  22.     memset(pos, 0, sizeof(pos));
  23.     for(int j = 1; j<=n; j++) pos[rk[j]]++;
  24.     for(int j = 1; j<=mx; j++) pos[j] += pos[j - 1];
  25.     for(int j = n; j; j--) sa[pos[rk[buckets[j]]]--] = buckets[j];
  26.     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]);
  27.     for(int j = 1; j<=n; j++) rk[j] = tmp[j];
  28.     mx = rk[sa[n]];
  29.     if(mx == n) break; //optimization to help run faster on 'sparser strings'
  30.   }
  31.  
  32. }
  33.  
  34. void make_lcp(){
  35.   for(int i = 1; i<=n; i++){
  36.         if(rk[i] == 1) cont;
  37.     lcp[rk[i]] = max(0, lcp[rk[i - 1]] - 1);
  38.     for(; str[i + lcp[rk[i]]] == str[sa[rk[i] - 1] + lcp[rk[i]]]; lcp[rk[i]]++);
  39.   }
  40. }
  41.  
  42. int main(){
  43.   cin.tie(0) -> sync_with_stdio(0);
  44.     cin >> (str + 1);
  45.     n = strlen(str + 1);
  46.     comp_SA();
  47.     make_lcp();
  48.     for(int i = 1; i<=n; i++){
  49.         int l = lcp[i], r = sa[i];
  50.         psum[l+1]++;
  51.         psum[r+1]--;
  52.     }  
  53.     for(int i = 1; i<=n; i++){
  54.         psum[i] += psum[i - 1];
  55.     }
  56.     for(int i = 1; i<=n; i++){
  57.         cout << psum[i] << " ";
  58.     }
  59.     cout << "\n";
  60.   return 0;
  61. }
RAW Paste Data