Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2020
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <stack>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <stdlib.h>
  8. #include <sstream>
  9. #include <string>
  10. #include <vector>
  11.  
  12. using namespace std;
  13.  
  14.  
  15. /*
  16. int fibbi(int n)
  17. {
  18. if (n <= 0)
  19. return 0;
  20.  
  21. if (n == 1)
  22. return 0;
  23.  
  24. if (n == 2)
  25. return 1;
  26.  
  27. if (n == 3)
  28. return 1;
  29.  
  30. if (n == 4)
  31. return 2;
  32.  
  33. vector<long long int> vec(n + 1, 0);
  34. vec[0] = 0;
  35. vec[1] = 0;
  36. vec[2] = 1;
  37. vec[3] = 1;
  38. vec[4] = 2;
  39.  
  40. for (auto i = 5; i < n + 1; i++)
  41. vec[i] = 1 + min(min(vec[i / 3] + i % 3, vec[i / 2] + i % 2), vec[i - 1]);
  42.  
  43. return vec[n];
  44. }
  45. */
  46.  
  47.  
  48. int main() {
  49.  
  50. int n, l = 0, r = -1, k = 0;
  51. long long answ = 0;
  52. string s;
  53. getline(cin, s);
  54. n = s.size();
  55. vector<int> vec(n + 1);
  56.  
  57. for (int i = 0; i < n; ++i) {
  58.  
  59. if (i > r)
  60. k = 1;
  61. else
  62. k = min(vec[l + r - i], r - i + 1);
  63. while (i + k < n & i - k >= 0 & s[i + k] == s[i - k])
  64. ++k;
  65.  
  66. vec[i] = k;
  67.  
  68. if (i + k - 1 > r)
  69. l = i - k + 1, r = i + k - 1;
  70.  
  71. }
  72.  
  73. vector<int> vec1(n);
  74. l = 0;
  75. r = -1;
  76.  
  77. for (int i = 0; i != n; ++i) {
  78.  
  79. if (i > r)
  80. k = 0;
  81. else
  82. k = min(vec1[l + r - i + 1], r - i + 1);
  83. while (i + k < n & i - k - 1 >= 0 & s[i + k] == s[i - k - 1])
  84. ++k;
  85.  
  86. vec1[i] = k;
  87.  
  88. if (i + k - 1 > r)
  89. l = i - k, r = i + k - 1;
  90.  
  91. }
  92.  
  93. for (int i = 0; i != n; i++) {
  94.  
  95. answ += vec[i] + vec1[i];
  96.  
  97. }
  98.  
  99. cout << answ;
  100.  
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement