Guest User

Untitled

a guest
Oct 16th, 2019
88
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