Advertisement
Guest User

Untitled

a guest
Oct 16th, 2019
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. string s, rs;
  9. int n;
  10. vector<int> p;
  11.  
  12. void preffix_function(string s, vector<int>& p){
  13.     int n = s.length();
  14.     p.assign(n,0);
  15.     for(int i = 1; i < n; ++i){
  16.         for(int j = p[i-1]; ;j = p[j-1]){
  17.             if(s[i]==s[j]){ p[i] = j+1; break;}
  18.             if(!j) break;
  19.         }
  20.     }
  21. }
  22.  
  23. int main(){
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.     cin >> n >> s;
  27.     rs = s;
  28.     reverse(rs.begin(),rs.end());
  29.     s = rs+"#"+s+s;
  30.     preffix_function(s,p);
  31.     if(*max_element(p.begin(),p.end())==n) cout << max_element(p.begin(),p.end())-p.begin()-2*n;
  32.     else cout << -1;
  33.  
  34.  
  35.     return 0;
  36.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement