fork(1) download
  1. /*
  2.   Задача "886. Суффиксы" с сайта 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.  
  15. typedef unsigned long long ull;
  16.  
  17. // Генерация случайного основания хэширования на отрезке (before, after):
  18. int gen_base(const int before, const int after) {
  19. auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  20. std::mt19937 mt_rand(seed);
  21. int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  22. return base % 2 == 0 ? base-1 : base;
  23. }
  24.  
  25. struct PolyHash {
  26. // -------- Статические переменные класса --------
  27. static const int mod = (int)1e9+123; // простой модуль полиномиального хэширования
  28. static std::vector<int> pow1; // степени основания base по модулю mod
  29. static std::vector<ull> pow2; // степени основания base по модулю 2^64
  30. static int base; // основание base
  31.  
  32. // --------- Статические функции класса ---------
  33. static inline int diff(int a, int b) { // разность a и b по модуль mod (Предполагается: 0 <= a < mod, 0 <= b < mod)
  34. return (a -= b) < 0 ? a + mod : a;
  35. }
  36.  
  37. // -------------- Переменные класса -------------
  38. std::vector<int> pref1; // Полиномиальный хэш на префиксе по модулю mod
  39. std::vector<ull> pref2; // Полиномиальный хэш на префиксе по модулю 2^64
  40.  
  41. // Конструктор от строки:
  42. PolyHash(const std::string& s)
  43. : pref1(s.size()+1u, 0)
  44. , pref2(s.size()+1u, 0)
  45. {
  46. assert(base < mod);
  47. const int n = s.size(); // Досчитываем необходимые степени основания по модулям хэширования
  48. while ((int)pow1.size() <= n) {
  49. pow1.push_back(1LL * pow1.back() * base % mod);
  50. pow2.push_back(pow2.back() * base);
  51. }
  52. for (int i = 0; i < n; ++i) { // Заполняем массив полиномиальных хэшей на префиксе
  53. assert(base > s[i]);
  54. pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  55. pref2[i+1] = pref2[i] + s[i] * pow2[i];
  56. }
  57. }
  58.  
  59. // Полиномиальный хэш подпоследовательности [pos, pos+len)
  60. // Если mxPow != 0, то происходит домножение значения до старшей степени base ^ mxPow
  61. inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  62. int hash1 = pref1[pos+len] - pref1[pos];
  63. ull hash2 = pref2[pos+len] - pref2[pos];
  64. if (hash1 < 0) hash1 += mod;
  65. if (mxPow != 0) {
  66. hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  67. hash2 *= pow2[mxPow-(pos+len-1)];
  68. }
  69. return std::make_pair(hash1, hash2);
  70. }
  71. };
  72.  
  73. // Инициализация статических объектов класса PolyHash:
  74. int PolyHash::base((int)1e9+7);
  75. std::vector<int> PolyHash::pow1{1};
  76. std::vector<ull> PolyHash::pow2{1};
  77.  
  78. // Вспомогательные функции для вычисления суммы вида: 1 + a + a^2 + ... + a^(k-1) по модулям mod и 2^64
  79. int sum_int(int a, int k) {
  80. if (k == 1) {
  81. return 1;
  82. } else if (k % 2 == 0) {
  83. return (1LL + a) * sum_int(1LL * a * a % PolyHash::mod, k / 2) % PolyHash::mod;
  84. } else {
  85. return 1 + (a+1LL) * a % PolyHash::mod * sum_int(1LL * a * a % PolyHash::mod, k / 2) % PolyHash::mod;
  86. }
  87. }
  88.  
  89. ull sum_ull(ull a, int k) {
  90. if (k == 1) {
  91. return 1;
  92. } else if (k % 2 == 0) {
  93. return (1 + a) * sum_ull(a * a, k / 2);
  94. } else {
  95. return 1 + a * sum_ull(a, k - 1);
  96. }
  97. }
  98.  
  99. int main() {
  100. static char buf[1+100000];
  101. scanf("%100000s", buf);
  102. std::string a(buf);
  103.  
  104. std::reverse(a.begin(), a.end());
  105.  
  106. // Генерация случайного основания хэширования:
  107. PolyHash::base = gen_base(256, PolyHash::mod);
  108.  
  109. // Строим полиномиальный хэш на префиксе исходной и развернутой строках:
  110. PolyHash hash(a);
  111.  
  112. // Длина строки:
  113. const int n = (int)a.size();
  114.  
  115. int answ = 0;
  116. for (int len = 1; len <= n; ++len) {
  117. // Получаем полиномиальный хэш:
  118. auto hash1 = hash(0, len); // на префиксе a[0...len)
  119. auto hash2 = hash(0, n); // на префиксе a[0...n)
  120.  
  121. // Домножаем хэш по модулю mod на соответствующие геометрические прогрессии:
  122. hash1.first = 1LL * hash1.first * sum_int(PolyHash::pow1[len], n) % PolyHash::mod;
  123. hash2.first = 1LL * hash2.first * sum_int(PolyHash::pow1[n], len) % PolyHash::mod;
  124.  
  125. // Домножаем хэш по модулю 2^64 на соответствующие геометрические прогрессии:
  126. hash1.second *= sum_ull(PolyHash::pow2[len], n);
  127. hash2.second *= sum_ull(PolyHash::pow2[n], len);
  128.  
  129. // Сравниваем хэши:
  130. answ += (hash1 == hash2);
  131. }
  132. printf("%d", answ);
  133.  
  134. return 0;
  135. }
Success #stdin #stdout 0s 4524KB
stdin
qqqqqqq
stdout
7