API tools faq
paste
Advertisement
ssrtatarin

Untitled

ssrtatarin
Jan 13th, 2022
18
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. typedef long long ll;
  5. typedef long double dl;
  6. const int N = 1e6;
  7. typedef __int128 lll;
  8.  
  9. ll f[N];
  10. ll s[N];
  11. ll step[N];
  12. int p = 29;
  13. ll mod = 1e9+21;
  14.  
  15.  
  16.  
  17. ll h(ll l, ll r){
  18. --l;
  19. ll h2 = (((f[r] - f[l] * step[r-l]) % mod) + mod) % mod;
  20. return h2;
  21. }
  22.  
  23. ll g_h2(ll l , ll r){
  24. --l;
  25. ll h2 = (((s[r] - s[l] * step[r-l]) % mod) + mod) % mod;
  26. return h2;
  27. }
  28.  
  29.  
  30. int main() {
  31. #ifdef anime
  32.  
  33. freopen("input1.txt", "r", stdin);
  34. freopen("outpu1.txt", "w", stdout);
  35. #endif
  36. string s1;
  37. cin >> s1;
  38.  
  39. s1 = '#' + s1 + '*';
  40. step[0] = 1;
  41. for(int i = 1; i < s1.size(); ++i){
  42. step[i] = (step[i-1]*p)%mod;
  43. }
  44. for(int i = 1; i < s1.size(); ++i){
  45. f[i] = ((s1[i] - 'a' + 1) +f[i-1]*p) % mod;
  46. }
  47. reverse(s1.begin(), s1.end());
  48. string s2 = s1;
  49. for(int i = 1; i < s2.size(); ++i){
  50. s[i] = ((s2[i] - 'a' + 1) + s[i-1]*p) % mod;
  51. }
  52. ll count = 0;
  53. for(int i = 1; i < s1.size(); ++i){
  54.  
  55. ll l = 0;
  56. ll q = s1.size()-i;
  57. ll r = 0;
  58. if(q>i) r = i;
  59. else r = q;
  60. while(r-l>1){
  61. ll mid = (l+r)/2;
  62. if(h(i, i+mid) == g_h2(s1.size()-i-1, s1.size()-i-1+mid)) l = mid;
  63. else r = mid;
  64. }
  65.  
  66. count+=l;
  67.  
  68.  
  69. }
  70. for(int i = 1; i < s1.size()-1; ++i){
  71.  
  72. ll l = 0;
  73. ll q = s1.size()-i;
  74. ll r = 0;
  75. if(q>i) r = i+1;
  76. else r = q;
  77. while(r-l>1){
  78. ll mid = (l+r)/2;
  79. if(h(i+1, i+mid) == g_h2(s1.size()-i-1, s1.size()-i-2+mid)) l=mid;
  80. else r = mid;
  81. }
  82. count+=l;
  83. }
  84. cout << count;
  85.  
  86. }
  87.  
  88.  
  89. // abaccab
  90. // // (s.size()-i+1)+mid;
  91.  
  92. // abacadba
  93. // abdacaba
  94.  
  95. // abacad
  96. // dacaba
  97. // m=2
  98. // i =4
  99.  
  100. // abadac
  101. // cadaba
  102.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!