SHARE
TWEET

Untitled

a guest Oct 16th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3. int main() {
  4.     int n;
  5.     cin >> n;
  6.     string s;
  7.     string sn = "";
  8.     cin >> s;
  9.     for(int i = n - 1; i >= 0; i--){
  10.         sn += s[i];
  11.     }
  12.  
  13.     const int p = 31;
  14.     int hashsn = 0;
  15.     long long p_pow = 1;
  16.     for (char i : sn) { // хэщ перевернутой строки
  17.         hashsn = int(((long long)hashsn +  (i - 'a' + 1) * p_pow) % int(1e9 + 7));
  18.         p_pow = p_pow * p;
  19.         if(p_pow > 1e9) p_pow = 31;
  20.     }
  21.     int pn = 0;
  22.     int hashs= 0;
  23.     p_pow = 1;
  24.     for (char i : s) { // хэш исходной строки
  25.         pn = p_pow;
  26.         hashs = int(((long long)hashs +  (i - 'a' + 1) * p_pow) % int(1e9 + 7));
  27.         p_pow =  (p_pow * p) % int(1e9 + 7);
  28.     }
  29.  
  30.     //int h = hashs;
  31.     for(int i = 0; i < n; i++){
  32.         if(i != 0){
  33.             hashs = (hashs - s[i - 1] + 'a' - 1) / p; // находим хэш циклического сдвига на 1 символ
  34.             hashs += pn * (s[i - 1] - 'a' + 1);
  35.         }
  36.         if(hashs == hashsn){
  37.             cout << i;
  38.             return 0;
  39.         }
  40.     }
  41.     cout << -1;
  42.     return 0;
  43. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top