fork download
copy 
  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
comments (?)
stdin
copy 
10
aaabaaaaaa
aaaaaaaaab
stdout
copy 
10
https://ideone.com/54x8SD
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!