fork(5) download
  1. /*
  2.   Задача "1157. Подпалиндромы" с сайта acmp.ru
  3.  
  4.   Решение: полиномиальный хэш, бинарный поиск, O(n log(n))
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <cassert>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <random>
  12. #include <chrono>
  13. #include <string>
  14. #include <iostream>
  15.  
  16. typedef unsigned long long ull;
  17.  
  18. // Генерация случайного основания хэширования на отрезке (before, after):
  19. int gen_base(const int before, const int after) {
  20. auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  21. std::mt19937 mt_rand(seed);
  22. int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  23. return base % 2 == 0 ? base-1 : base;
  24. }
  25.  
  26. struct PolyHash {
  27. // -------- Статические переменные класса --------
  28. static const int mod = (int)1e9+123; // простой модуль полиномиального хэширования
  29. static std::vector<int> pow1; // степени основания base по модулю mod
  30. static std::vector<ull> pow2; // степени основания base по модулю 2^64
  31. static int base; // основание base
  32.  
  33. // --------- Статические функции класса ---------
  34. static inline int diff(int a, int b) { // разность a и b по модуль mod (Предполагается: 0 <= a < mod, 0 <= b < mod)
  35. return (a -= b) < 0 ? a + mod : a;
  36. }
  37.  
  38. // -------------- Переменные класса -------------
  39. std::vector<int> pref1; // Полиномиальный хэш на префиксе по модулю mod
  40. std::vector<ull> pref2; // Полиномиальный хэш на префиксе по модулю 2^64
  41.  
  42. // Конструктор от строки:
  43. PolyHash(const std::string& s)
  44. : pref1(s.size()+1u, 0)
  45. , pref2(s.size()+1u, 0)
  46. {
  47. assert(base < mod);
  48. const int n = s.size(); // Досчитываем необходимые степени основания по модулям хэширования
  49. while ((int)pow1.size() <= n) {
  50. pow1.push_back(1LL * pow1.back() * base % mod);
  51. pow2.push_back(pow2.back() * base);
  52. }
  53. for (int i = 0; i < n; ++i) { // Заполняем массив полиномиальных хэшей на префиксе
  54. assert(base > s[i]);
  55. pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  56. pref2[i+1] = pref2[i] + s[i] * pow2[i];
  57. }
  58. }
  59.  
  60. // Полиномиальный хэш подпоследовательности [pos, pos+len)
  61. // Если mxPow != 0, то происходит домножение значения до старшей степени base ^ mxPow
  62. inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  63. int hash1 = pref1[pos+len] - pref1[pos];
  64. ull hash2 = pref2[pos+len] - pref2[pos];
  65. if (hash1 < 0) hash1 += mod;
  66. if (mxPow != 0) {
  67. hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  68. hash2 *= pow2[mxPow-(pos+len-1)];
  69. }
  70. return std::make_pair(hash1, hash2);
  71. }
  72. };
  73.  
  74. // Инициализация статических объектов класса PolyHash:
  75. int PolyHash::base((int)1e9+7);
  76. std::vector<int> PolyHash::pow1{1};
  77. std::vector<ull> PolyHash::pow2{1};
  78.  
  79. int main() {
  80. static char buf[1+100000];
  81. scanf("%1000000s", buf);
  82. std::string a(buf);
  83. std::string b(a);
  84. std::reverse(b.begin(), b.end());
  85.  
  86. // Генерация случайного основания хэширования:
  87. PolyHash::base = gen_base(256, PolyHash::mod);
  88.  
  89. // Строим полиномиальный хэш на префиксе исходной и развернутой строках:
  90. PolyHash hash_a(a), hash_b(b);
  91.  
  92. // Длина строк (также mxPow)
  93. const int n = (int)a.size();
  94.  
  95. ull answ = 0;
  96. for (int i = 0, j = n-1; i < n; ++i, --j) {
  97. // Палиндром нечетной длины:
  98. int low = 0, high = std::min(n-i, n-j)+1;
  99. while (high - low > 1) {
  100. int mid = (low + high) / 2;
  101. if (hash_a(i, mid, n) == hash_b(j, mid, n)) {
  102. low = mid;
  103. } else {
  104. high = mid;
  105. }
  106. }
  107. answ += low;
  108. // Палиндром четной длины:
  109. low = 0, high = std::min(n-i-1, n-j)+1;
  110. while (high - low > 1) {
  111. int mid = (low + high) / 2;
  112. if (hash_a(i+1, mid, n) == hash_b(j, mid, n)) {
  113. low = mid;
  114. } else {
  115. high = mid;
  116. }
  117. }
  118. answ += low;
  119. }
  120. std::cout << answ;
  121. return 0;
  122. }
Success #stdin #stdout 0s 4472KB
stdin
ABACABADABACABA
stdout
32