fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int min_cyc(string s)
  7. {
  8.     int p = 0;
  9.     s += s;
  10.  
  11.     vector<int> f(s.size(), -1);
  12.     for (int l = 1, r = 1; r < s.size(); ++r) 
  13.     {
  14.         for (l = f[r - p - 1];     l != -1 && s[p + l + 1] != s[r];l = f[l] )
  15.             if (s[l + p + 1] > s[r])
  16.                 p = r - l - 1;
  17.  
  18.         if (l == -1 && s[p + l + 1] != s[r])
  19.         {
  20.             if (s[p + l + 1] > s[r])
  21.                 p = r;
  22.  
  23.             f[r - p] = -1;
  24.         }
  25.         else
  26.         {
  27.             f[r - p] = l + 1;
  28.         }
  29.     }
  30.  
  31.     return p;
  32. }
  33.  
  34. int main()
  35. {
  36.     string s;
  37.     cin >> s;
  38.     cout << min_cyc(s);
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
adaada
stdout
copy 
2
https://ideone.com/nIDIVF
language:
C++ (gcc 8.3)
created:
7 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!