fork download
copy 
  1. //Dai Ca Di Hoc
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define reset(x) memset(x, 0,sizeof(x))
  5. #define MIN(x,y) if (x > (y)) x = (y)
  6. #define MAX(x,y) if (x < (y)) x = (y)
  7. #define PB push_back
  8. #define mp make_pair
  9. #define F first
  10. #define S second
  11. #define Task "divseq"
  12. #define maxn 300005
  13. #define MOD 1000000007
  14. #define remain(x) if (x > MOD) x -= MOD
  15. #define pii pair<int, int>
  16.  
  17. using namespace std;
  18.  
  19. string s;
  20. int n, zmax = 0;
  21. int z[maxn], c[maxn];
  22.  
  23. void z_function () {
  24.     z[0] = 0;
  25.     for (int k=1, l=0, r=0; k<n; ++k) {
  26.         // chuan bi gia tri x toi thieu
  27.         int x = 0;
  28.         if (k <= r) x = min(r-k+1, z[k-l]);
  29.         // mo rong doan
  30.         while (k+x < n && s[x] == s[k+x]) x++;
  31.         // ghi nhan, cap nhat
  32.         z[k] = x;
  33.         if (k+x-1 > r)
  34.             l = k,  r = k+x-1;
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40.  
  41. 	ios_base::sync_with_stdio(0);
  42.     freopen(Task".inp", "r", stdin);
  43.     freopen(Task".out", "w", stdout);
  44.     z_function();
  45.     return 0;
  46. }
  47.  
  48.  
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RAaYDL
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

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!