fork download
  1. #include <stdio.h>
  2. #include <cassert>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <random>
  6. #include <chrono>
  7. #include <string>
  8. #include <iostream>
  9.  
  10. typedef unsigned long long ull;
  11.  
  12. // Генерация случайного основания в (before, after) открытом интервале:
  13. int gen_base(const int before, const int after) {
  14. auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  15. std::mt19937 mt_rand(seed ^ ull(new ull));
  16. int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  17. return base % 2 == 0 ? base-1 : base;
  18. }
  19.  
  20. struct PolyHash {
  21. // -------- Статические переменные --------
  22. static const int MOD = 2147483647;
  23. static std::vector<int> pow1; // степени основания по модулю MOD
  24. static std::vector<ull> pow2; // степени основания по модулю 2^64
  25. static int base; // основание (точка) хэширования
  26.  
  27. // --------- Статические функции --------
  28. static inline int diff(int a, int b) {
  29. // Разность между `a` и `b` по модулю MOD (0 <= a < MOD, 0 <= b < MOD)
  30. return (a -= b) < 0 ? a + MOD : a;
  31. }
  32.  
  33. static inline int mod(ull x) {
  34. // Смещенный остаток от деления x на MOD (только для MOD = 2^31-1):
  35. x += MOD;
  36. x = (x >> 31) + (x & MOD);
  37. return int((x >> 31) + (x & MOD));
  38. }
  39.  
  40. // -------------- Переменные класса -------------
  41. std::vector<int> pref1; // Полиномиальный хэш на префиксе по модулю MOD
  42. std::vector<ull> pref2; // Полиномиальный хэш на префиксе по модулю 2^64
  43.  
  44. // Конструктор от строчки:
  45. PolyHash(const std::string& s)
  46. : pref1(s.size()+1u, 0)
  47. , pref2(s.size()+1u, 0)
  48. {
  49. // Предподсчет степеней основания:
  50. while (pow1.size() <= s.size()) {
  51. pow1.push_back(mod((ull)pow1.back() * base));
  52. pow2.push_back(pow2.back() * base);
  53. }
  54. // Заполнение массивов с хэшем на префиксе:
  55. for (int i = 0; i < (int)s.size(); ++i) {
  56. pref1[i+1] = mod(pref1[i] + (ull)s[i] * pow1[i]);
  57. pref2[i+1] = pref2[i] + s[i] * pow2[i];
  58. }
  59. }
  60.  
  61. // Полиномиальный хэш от подпоследовательности [pos, pos+len)
  62. // Если mxPow != 0, значение автоматически домножается на основание в
  63. // нужной степени при доведении до степени base ^ mxPow:
  64. inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  65. int hash1 = diff(pref1[pos+len], pref1[pos]);
  66. ull hash2 = pref2[pos+len] - pref2[pos];
  67. if (mxPow != 0) {
  68. hash1 = mod((ull)hash1 * pow1[mxPow-(pos+len-1)]);
  69. hash2 *= pow2[mxPow-(pos+len-1)];
  70. }
  71. return std::make_pair(hash1, hash2);
  72. }
  73.  
  74. // Полиномиальный хэш на префиксе [0, len) после обмена символов ci и cj на
  75. // позициях i и j:
  76. inline std::pair<int, ull> prefix_after_swap(const int len, const int i, const int j, const char ci, const char cj) const {
  77. // Префикс до i:
  78. int hash1 = pref1[std::min(len, i)];
  79. ull hash2 = pref2[std::min(len, i)];
  80. if (len <= i) return std::make_pair(hash1, hash2);
  81. // Добавления символа cj на позицию i:
  82. hash1 = mod(hash1 + (ull)cj * pow1[i]);
  83. hash2 += cj * pow2[i];
  84. // Префикс до j:
  85. hash1 = mod(hash1 + (ull)diff(pref1[std::min(len, j)], pref1[i+1]));
  86. hash2 += pref2[std::min(len,j)] - pref2[i+1];
  87. if (len <= j) return std::make_pair(hash1, hash2);
  88. // Добавление символа на позицию j:
  89. hash1 = mod(hash1 + (ull)ci * pow1[j]);
  90. hash2 += ci * pow2[j];
  91. // Префикс до len:
  92. hash1 = mod(hash1 + (ull)diff(pref1[len], pref1[j+1]));
  93. hash2 += pref2[len] - pref2[j+1];
  94. return std::make_pair(hash1, hash2);
  95. }
  96. };
  97.  
  98. // Инициализация статических переменных класса:
  99. int PolyHash::base((int)1e9+7);
  100. std::vector<int> PolyHash::pow1{1};
  101. std::vector<ull> PolyHash::pow2{1};
  102.  
  103. int solve(const int n, const std::string& s, const std::string& t) {
  104. // Генерация случайного основания:
  105. PolyHash::base = gen_base(256, PolyHash::MOD);
  106.  
  107. // Построение полиномиального хэша на строках S и T:
  108. PolyHash hash_s(s), hash_t(t);
  109.  
  110. // Поиск первого несовпадающего символа:
  111. int pos1 = 0;
  112. while (pos1 < n && s[pos1] == t[pos1]) ++pos1;
  113.  
  114. // Пытаемся поменять pos1 с каждым символом после pos2 по очереди:
  115. int answ = pos1;
  116. for (int pos2 = pos1+1; pos2 < n; ++pos2) {
  117. // Применяем бинарный поиск для нахождения наибольшего общего префикса после обмена:
  118. int low = 0, high = n+1;
  119. while (high-low > 1) {
  120. const int mid = (low + high) / 2;
  121. const auto hs = hash_s.prefix_after_swap(mid, pos1, pos2, s[pos1], s[pos2]);
  122. if (hs == hash_t(0, mid)) {
  123. low = mid;
  124. } else {
  125. high = mid;
  126. }
  127. }
  128. // Обновляем ответ:
  129. answ = std::max(answ, low);
  130. }
  131. return answ;
  132. }
  133.  
  134. int main() {
  135. // Чтение:
  136. int n;
  137. scanf("%d", &n);
  138. char buf[1+200000];
  139. scanf("%200000s", buf);
  140. std::string s(buf);
  141. scanf("%200000s", buf);
  142. std::string t(buf);
  143. // Решение задачи и вывод ответа:
  144. printf("%d", solve(n,s,t));
  145. return 0;
  146. }
Success #stdin #stdout 0s 4356KB
stdin
10
aaabaaaaaa
aaaaaaaaab
stdout
10