fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. #define pii pair<int, int>
  4. #define f first
  5. #define s second
  6. #define all(x) x.begin(), x.end()
  7. using namespace std;
  8.  
  9. const int maxn = 4e5 + 10;
  10. const int maxq = 5e5 + 10;
  11. const int LOG = log2(maxn)+2;
  12. int n;
  13.  
  14. pair<pii, int> L[maxn]; //Lexicography order: of string at position have rank i -> start at position L[i].second
  15. int R[LOG][maxn]; //Ranking of string start at position i, have length of 2^log -> have rank R[log][i]
  16. int SA[maxn];
  17.  
  18. void build_SA(const string& s){
  19.     up(i,1,n) R[0][i] = s[i];
  20.  
  21.     for (int POW = 1; (1 << (POW-1)) <= n; POW++){
  22.         up(i,1,n){
  23.             L[i].f.f = R[POW-1][i];
  24.             int k = i + (1 << (POW-1));
  25.             if (k <= n) L[i].f.s = R[POW-1][k];
  26.             else L[i].f.s = -1;
  27.             L[i].s = i;
  28.         }
  29.         sort(L+1, L+n+1);
  30.  
  31.         int cnt = 0;
  32.         up(i,1,n){
  33.             if (L[i].f == L[i-1].f) R[POW][L[i].s] = R[POW][L[i-1].s];
  34.             else R[POW][L[i].s] = ++cnt;
  35.         }
  36.     }
  37.  
  38.     up(i,1,n) SA[i] = L[i].s;
  39. }
  40.  
  41. int LCP[maxn];
  42. int pos[maxn];
  43. void Kasai(const int SA[], const string& s){
  44.     up(i,1,n) pos[SA[i]] = i;
  45.  
  46.     int k = 0;
  47.     up(i,1,n){
  48.         int& cur = pos[i];
  49.         int j = SA[cur-1];
  50.         //if suffix pair at position (i, j), have rank (cur, cur-1) and LCP equal to k
  51.         //then suffix pair at position (i+1, j'), have rank(cur', cur'-1) should have LCP at least k-1, and at most...
  52.         //find at at most on this line :)
  53.         while (i+k <= n && j+k <= n && s[i+k] == s[j+k]) ++k;
  54.         LCP[cur] = k;
  55.         if (k) --k;
  56.     }
  57. }
  58.  
  59. int sp[LOG][maxn];
  60. int logg[maxn];
  61. void build_sparse(){
  62.     up(i,1,n) sp[0][i] = LCP[i];
  63.     up(i,2,n) logg[i] = logg[(i >> 1)] + 1;
  64.     for (int i = 1; (1 << i) <= n; i++){
  65.         for (int j = 1; j + (1 << i) - 1 <= n; j++){
  66.             sp[i][j] = min(sp[i-1][j], sp[i-1][j + (1 << (i-1))]);
  67.         }
  68.     }
  69. }
  70.  
  71. int RMQ(const int& l, const int& r){
  72.     int k = logg[r - l + 1];
  73.     return min(sp[k][l], sp[k][r - (1 << k) + 1]);
  74. }
  75.  
  76. int get_left(int u, const int& need){
  77.     int l = 0;
  78.     int r = u;
  79.     while (r - l > 1){
  80.         int mid = (l+r) >> 1;
  81.         if (RMQ(mid, u) >= need) r = mid;
  82.         else l = mid;
  83.     }
  84.     if (LCP[r] >= need) return r-1;
  85.     return r;
  86. } // Find from [1 -> u]
  87.  
  88. int get_right(int u, const int& need){
  89.     ++u;
  90.     int l = u;
  91.     int r = n+1;
  92.     while (r - l > 1){
  93.         int mid = (l+r) >> 1;
  94.         if (RMQ(u, mid) >= need) l = mid;
  95.         else r = mid;
  96.     }
  97.  
  98.     if (LCP[l] >= need) return l;
  99.     return l-1;
  100. } // Find from [u+1 -> n]
  101.  
  102. int BIT[maxn];
  103. void update(int x, const int val){
  104.     while (x <= n){
  105.         BIT[x] += val;
  106.         x += (x & (-x));
  107.     }
  108. }
  109.  
  110. int get(int x){
  111.     int res = 0;
  112.     while (x){
  113.         res += BIT[x];
  114.         x -= (x & (-x));
  115.     }
  116.     return res;
  117. }
  118.  
  119. struct event{
  120.     int L,R,id,SIGN;
  121.     event(int L, int R, int id, int SIGN):
  122.         L(L), R(R), id(id), SIGN(SIGN)
  123.     {}
  124. };
  125. vector<event> E[maxn];
  126.  
  127. int ans[maxq];
  128. void solve(){
  129.     up(i,1,n){
  130.         update(SA[i], 1);
  131.         for (auto e : E[i]){
  132.             int L = e.L;
  133.             int R = e.R;
  134.             int id = e.id;
  135.             int SIGN = e.SIGN;
  136.             ans[id] += SIGN * (get(R) - get(L-1));
  137.         }
  138.     }
  139. }
  140.  
  141. signed main(){
  142.     ios_base::sync_with_stdio(false);
  143.     cin.tie(0);
  144.     #define Task "A"
  145.     if (fopen(Task".inp", "r")){
  146.         freopen(Task".inp", "r", stdin);
  147.         freopen(Task".out", "w", stdout);
  148.     }
  149.  
  150.     string s,t;
  151.     cin >> s >> t;
  152.     int SSIZE = s.size();
  153.  
  154.     string g = "@" + s + t;
  155.     n = g.size() - 1;
  156.  
  157.     build_SA(g);
  158.     Kasai(SA, g);
  159.  
  160.     build_sparse();
  161.  
  162.     int q;
  163.     cin >> q;
  164.     up(i,1,q){
  165.         int sl, sr, tl, tr;
  166.         cin >> sl >> sr >> tl >> tr;
  167.         int slen = sr - sl + 1;
  168.         int L = get_left(pos[sl], slen);
  169.         int R = get_right(pos[sl], slen);
  170.         int A = tl + SSIZE;
  171.         int B = tr + SSIZE - slen + 1;
  172.  
  173.         if (B < A || R < L) continue;
  174.         E[L-1].emplace_back(event(A, B, i, -1));
  175.         E[R].emplace_back(event(A, B, i, 1));
  176.     }
  177.  
  178.     solve();
  179.     up(i,1,q) cout << ans[i] << "\n";
  180. }
  181.  
Success #stdin #stdout 0.01s 38528KB
comments (?)
stdin
copy 
abb
ababababb
5
1 2 1 7
2 3 2 9
3 3 4 7
1 2 2 4
1 1 1 9
stdout
copy 
3
1
2
1
4
https://ideone.com/NYTrhb
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!