fork download
copy 
  1. /*
  2.     Solution: polynomial hashes + binary search, O(n * log(n))
  3. */
  4.  
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <string>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <cassert>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <functional>
  14.  
  15. typedef unsigned long long ull;
  16.  
  17. // -----------------------------------------------------------------------------
  18. bool is_prime(int n) {
  19.     for (int i = 2; i * i <= n; ++i) {
  20.         if (n % i == 0) {
  21.             return false;
  22.         }
  23.     }
  24.     return n > 1;
  25. }
  26. // -----------------------------------------------------------------------------
  27. int next_prime(int number, int steps = 1) {
  28.     while (steps--) {
  29.         while (!is_prime(++number));
  30.     }
  31.     return number;
  32. }
  33. // -----------------------------------------------------------------------------
  34.  
  35. int solve(const std::string& s, const std::string& t) {
  36.     // Constants of hashing:
  37.     const int base = next_prime(256, std::rand() % 77 + 33);
  38.     const int mod1 = next_prime(1e9, std::rand() % 77 + 33);
  39.     const int n = (int)s.size();
  40.     const int mxPow = n;
  41.  
  42.     // Calculation powers of base:
  43.     std::vector<int> pow1(1+mxPow, 1);
  44.     std::vector<ull> pow2(1+mxPow, 1);
  45.     for (int i = 1; i <= mxPow; ++i) {
  46.         pow1[i] = 1LL * pow1[i-1] * base % mod1;
  47.         pow2[i] = pow2[i-1] * base;
  48.     }
  49.  
  50.     // Find hashes on prefixes s and t:
  51.     std::vector<int> s_pref1{0}, t_pref1{0};
  52.     std::vector<ull> s_pref2{0}, t_pref2{0};
  53.     for (int i = 0; i < n; ++i) {
  54.         // Hash modulo mod1:
  55.         s_pref1.push_back((s_pref1.back() + 1LL * s[i] * pow1[i]) % mod1);
  56.         t_pref1.push_back((t_pref1.back() + 1LL * t[i] * pow1[i]) % mod1);
  57.         // Hash modulo mod2 = 2^64:
  58.         s_pref2.push_back(s_pref2.back() + s[i] * pow2[i]);
  59.         t_pref2.push_back(t_pref2.back() + t[i] * pow2[i]);
  60.     }
  61.  
  62.     // Find first not equal symbol:
  63.     int f = 0;
  64.     while (f < n && s[f] == t[f]) ++f;
  65.  
  66.     std::function<std::pair<int, ull>(int,int,int)> hash_on_prefix_after_swap = [&] (const int r, const int f, const int l) {
  67.         // Function for calculating polynomial hash on substring s[0..r] after swap s[f] and s[l]
  68.         int hash1 = 0; ull hash2 = 0;
  69.         // Add hash on s[0, f);
  70.         hash1 += s_pref1[std::min(r+1, f)];
  71.         hash2 += s_pref2[std::min(r+1, f)];
  72.         if (r < f) return std::make_pair(hash1, hash2);
  73.         // Add s[l]:
  74.         hash1 = (hash1 + 1LL * s[l] * pow1[f]) % mod1;
  75.         hash2 += s[l] * pow2[f];
  76.         if (r == f) return std::make_pair(hash1, hash2);
  77.         // Add hash on s[f+1, l): 
  78.         hash1 = (0LL + hash1 + s_pref1[std::min(l, r+1)] - s_pref1[f+1] + mod1) % mod1;
  79.         hash2 += s_pref2[std::min(l, r+1)] - s_pref2[f+1];
  80.         if (r < l) return std::make_pair(hash1, hash2);
  81.         // Add s[f]:
  82.         hash1 = (hash1 + 1LL * s[f] * pow1[l]) % mod1;
  83.         hash2 += s[f] * pow2[l];
  84.         if (r == l) return std::make_pair(hash1, hash2);
  85.         // Add s[l+1, r]:
  86.         hash1 = (0LL + hash1 + s_pref1[r+1] - s_pref1[l+1] + mod1) % mod1;
  87.         hash2 += s_pref2[r+1] - s_pref2[l+1];
  88.         return std::make_pair(hash1, hash2);
  89.     };    
  90.  
  91.     // Try to change the first unequal symbol with all that stand after:
  92.     int answ = f;
  93.     for (int l = f+1; l < n; ++l) {
  94.         // Binary search: s[0..low] == t[0..low], s[0..high] != t[0..high]
  95.         int low = f-1, high = n;
  96.         while (high - low > 1) {
  97.             int mid = (low + high) / 2;
  98.             auto h1 = hash_on_prefix_after_swap(mid, f, l);
  99.             if (h1.first == t_pref1[mid+1] && h1.second == t_pref2[mid+1]) {
  100.                 low = mid;
  101.             } else {
  102.                 high = mid;
  103.             }            
  104.         }
  105.         // Update answer:
  106.         answ = std::max(answ, low+1);
  107.     }
  108.     return answ;
  109. }
  110.  
  111. int main() {
  112.     std::srand(std::time(0));
  113.     std::ios_base::sync_with_stdio(false);
  114.     std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
  115.  
  116.     int n; 
  117.     std::cin >> n;
  118.     std::string s, t;
  119.     std::cin >> s >> t;
  120.     assert(s.size() == t.size());
  121.     std::cout << solve(s, t);
  122.     return 0; 
  123. }
Success #stdin #stdout 0.01s 4492KB
comments (?)
stdin
copy 
3
wai
add
stdout
copy 
1
https://ideone.com/DJklta
language:
C++14 (gcc 8.3)
created:
6 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!