fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14.  
  15. const ll Mod[2] = {(ll)1e9+7,(ll)1e9+3};
  16. const ll Maxn = 1e6+69;
  17. const ll oo = 1e18;
  18.  
  19. const ll base = 31;
  20.  
  21. string s ;
  22. pll p[Maxn],h[Maxn];
  23.  
  24. pll Mod2 ( pll x )
  25. {
  26.     return {x.fi%Mod[0],x.se%Mod[1]};
  27. }
  28.  
  29. void Init()
  30. {
  31.     p[0] = {1,1} ;
  32.     for (int i = 1 ; i <= s.size(); ++i)
  33.     {
  34.         p[i] = Mod2({p[i-1].fi*base,p[i-1].se*base});
  35.         h[i] = Mod2({h[i-1].fi*base+s[i-1]-'a'+1,
  36.                     h[i-1].se*base+s[i-1]-'a'+1});
  37.     }
  38. }
  39.  
  40. ll Get ( int l , int r )
  41. {
  42.     ll x1 = h[r].fi - h[l-1].fi*p[r-l+1].fi ;
  43.     ll x2 = h[r].se - h[l-1].se*p[r-l+1].se;
  44.     return (x1+ Mod[0]*Mod[0])%Mod[0]*Mod[0]+
  45.     (x2+Mod[1]*Mod[1])%Mod[1];
  46. }
  47.  
  48. bool Check ( int leng )
  49. {
  50.     vector<ll> v ;
  51.     for (int i = 1 ; i <= s.size()-leng+1; ++i)
  52.     {
  53.         ll cur = Get(i,i+leng-1);
  54.         v.pb(cur);
  55.     }
  56.     sort(v.begin(),v.end());
  57.     for (int i = 0 ; i < v.size()-1; ++i)
  58.     {
  59.         if(v[i]==v[i+1]) return true;
  60.     }
  61.     return false;
  62. }
  63.  
  64. void Print ( int leng )
  65. {
  66.     vector<pll> v ;
  67.     for (int i = 1 ; i <= s.size()-leng+1; ++i)
  68.     {
  69.         ll cur = Get(i,i+leng-1);
  70.         v.pb({cur,i-1});
  71.     }
  72.     sort(v.begin(),v.end());
  73.     for (int i = 0 ; i < v.size()-1; ++i)
  74.     {
  75.         if(v[i].fi==v[i+1].fi)
  76.         {
  77.             cout << s.substr(v[i].se,leng);
  78.             return;
  79.         }
  80.     }
  81. }
  82.  
  83. void Do()
  84. {
  85.     getline(cin,s);
  86.     Init();
  87.     ll l = 1 , r = s.size();
  88.     while(l<=r)
  89.     {
  90.         ll mid = (l+r)/2;
  91.         if(Check(mid)) l = mid+1;
  92.         else r = mid - 1;
  93.     }
  94.     if(r==0)
  95.     {
  96.         cout << -1;
  97.         return;
  98.     }
  99.     Print(r);
  100. }
  101.  
  102. signed main ()
  103. {
  104.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  105. #define task "test"
  106. if(fopen(task".inp", "r")){
  107.         freopen(task".inp", "r", stdin);
  108.         freopen(task".out", "w", stdout);
  109.     }
  110.     int ntest=1;
  111.     while(ntest--) Do();
  112.  
  113.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  114. }
  115.  
Success #stdin #stdout #stderr 0.01s 5672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
stderr
copy 
Time elapsed: 6ms
https://ideone.com/RZOZOF
language:
C++14 (gcc 8.3)
created:
19 days 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!