Advertisement
Guest User

Untitled

a guest
Nov 19th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include <set>
  2. #include <map>
  3. #include <deque>
  4. #include <cmath>
  5. #include <queue>
  6. #include <string>
  7. #include <vector>
  8. #include <iostream>
  9. #include <algorithm>
  10.  
  11. #define pb push_back
  12. #define po pop_back()
  13. #define matrix vector<vector<ll>>
  14. #define pin(p) cin >> p.first >> p.second;
  15. #define mx(v) max_element(v.begin(), v.end());
  16. #define mn(v) min_element(v.begin(), v.end());
  17. #define pout(p) cout << p.first << " " << p.second;
  18. #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
  19. #define vin(v, n) for(int i = 0; i < n; ++i) cin >> v[i];
  20. #define vout(v, n) for(int i = 0; i < n; ++i) cout << v[i];
  21.  
  22. using namespace std;
  23.  
  24. typedef long long ll;
  25. typedef long long ld;
  26.  
  27. const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
  28. const int inf = 1000 * 1000 * 1000;
  29. vector<ll> hashe(100000);
  30. vector<ll> power(100000);
  31. ll truehash(int l, int r)
  32. {
  33. return hashe[r + 1] - hashe[l] * power[r - l + 1];
  34. }
  35. bool turehash(int len,string &s)
  36. {
  37. return len <= s.size() / 2 ? truehash(0, len - 1) == truehash(len, len * 2 - 1) : true;
  38. }
  39. int main()
  40. {
  41. string s;
  42. cin >> s;
  43. s.insert(s.begin(), '#');
  44. hashe[0] = 0;
  45. power[0] = 1;
  46. for (int i = 1; i < s.size(); ++i)
  47. {
  48. power[i] = power[i - 1] * 29;
  49. hashe[i] = hashe[i - 1] + (s[i] - 'a' + 1)*power[i];
  50. }
  51. for (int k = 1; k < s.size(); ++k)
  52. {
  53. if (turehash(k,s))
  54. {
  55. cout << k;
  56. return 0;
  57. }
  58. }
  59. cout << s.size()-1;
  60. system("pause");
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement