Saleh127

Substring Frequency Suffix array using counting sort

May 21st, 2022 (edited)
561
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-05-22-10.21.44
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. void count_sort(vector<int> &p, const vector<int> &c,int n)
  13. {
  14.     vector<int> p_new(n), cnt(n + 1);
  15.     for(int x : c) cnt[x + 1]++;
  16.     for(int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
  17.     for(int x : p) p_new[cnt[c[x]]++] = x;
  18.     p = p_new;
  19. }
  20.  
  21.  
  22. vector<int> sac(string &s)
  23. {
  24.     s += '$';
  25.     int n = s.length();
  26.     vector<int> p(n), c(n);
  27.     {
  28.         vector<pair<char, int>> a(n);
  29.         for (int i = 0; i < n; i++)
  30.         {
  31.             a[i] = {s[i], i};
  32.         }
  33.         sort(a.begin(), a.end());
  34.         for (int i = 0; i < n; i++)
  35.         {
  36.             p[i] = a[i].second;
  37.         }
  38.  
  39.         c[p[0]] = 0;
  40.  
  41.         for (int i = 1; i < n; i++)
  42.         {
  43.             if (a[i].first == a[i - 1].first)
  44.                 c[p[i]] = c[p[i - 1]];
  45.             else
  46.                 c[p[i]] = c[p[i - 1]] + 1;
  47.         }
  48.     }
  49.     int k = 0;
  50.     while ((1 << k) < n)
  51.     {
  52.         for (int i = 0; i < n; i++)
  53.         {
  54.             p[i] = (p[i] - (1 << k) + n) % n;
  55.         }
  56.         count_sort(p, c, n);
  57.  
  58.         vector<int> c_new(n);
  59.  
  60.         c_new[p[0]] = 0;
  61.         for (int i = 1; i < n; i++)
  62.         {
  63.             pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + (1 << k)) % n]};
  64.             pair<int, int> now = {c[p[i]], c[(p[i] + (1 << k)) % n]};
  65.             if (now == prev)
  66.                 c_new[p[i]] = c_new[p[i - 1]];
  67.             else
  68.                 c_new[p[i]] = c_new[p[i - 1]] + 1;
  69.         }
  70.         k++;
  71.         c = c_new;
  72.     }
  73.  
  74.     //p.erase(p.begin());
  75.  
  76.     return p;
  77. }
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0);
  83.     cout.tie(0);
  84.  
  85.  
  86.  
  87.     string s;
  88.     cin >> s;
  89.     vector<int> sa = sac(s);
  90.     int n = s.size();
  91.  
  92.  
  93.     int q;
  94.     cin>>q;
  95.     auto cmp1 = [&](string b,int a){return b < s.substr(a,b.size());};
  96.     auto cmp2 = [&](int a,string b){return s.substr(a,b.size()) < b;};
  97.     while(q--){
  98.         string t;
  99.         cin>>t;
  100.         int z = upper_bound(sa.begin(),sa.end(),t,cmp1) - lower_bound(sa.begin(),sa.end(),t,cmp2);
  101.         cout<<z<<"\n";
  102.     }
  103.  
  104.  
  105.     get_lost_idiot;
  106. }
  107.  
RAW Paste Data Copied