fork download
copy 
  1. /*
  2.     Problem: https://w...content-available-to-author-only...k.com/contests/ab-yeh-kar-ke-dikhao/challenges/jitu-and-strings
  3.     
  4.     Solution: polynomial hashes + binary search, O(n * log(n))
  5. */
  6.  
  7. #include <iostream>
  8. #include <string>
  9. #include <vector>
  10. #include <algorithm>
  11. #include <cassert>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <functional>
  15.  
  16. const int SINGLE_HASH = 0, DOUBLE_HASH = 1;
  17.  
  18. typedef unsigned long long ull;
  19.  
  20. // -----------------------------------------------------------------------------
  21. bool is_prime(int n) {
  22.     for (int i = 2; i * i <= n; ++i) {
  23.         if (n % i == 0) {
  24.             return false;
  25.         }
  26.     }
  27.     return n > 1;
  28. }
  29. // -----------------------------------------------------------------------------
  30. int next_prime(int number, int steps = 1) {
  31.     while (steps--) {
  32.         while (!is_prime(++number));
  33.     }
  34.     return number;
  35. }
  36. // -----------------------------------------------------------------------------
  37.  
  38. int solve(const std::string& s, const std::string& t, const int HASH_TYPE) {    
  39.     // Constants of hashing:
  40.     const int base = next_prime(256, std::rand() % 77 + 33);
  41.     const int mod1 = next_prime(1e9, std::rand() % 77 + 33);
  42.     const int n = (int)s.size();
  43.     const int mxPow = n;
  44.  
  45.     // Calculation powers of base:
  46.     std::vector<int> pow1(1+mxPow, 1);
  47.     std::vector<ull> pow2(1+mxPow, 1);
  48.     for (int i = 1; i <= mxPow; ++i) {
  49.         pow1[i] = 1LL * pow1[i-1] * base % mod1;
  50.         pow2[i] = pow2[i-1] * base;
  51.     }
  52.  
  53.     // Find hashes on prefixes s and t:
  54.     std::vector<int> s_pref1{0}, t_pref1{0};
  55.     std::vector<ull> s_pref2{0}, t_pref2{0};
  56.     for (int i = 0; i < n; ++i) {
  57.         // Hash modulo mod1:
  58.         s_pref1.push_back((s_pref1.back() + 1LL * s[i] * pow1[i]) % mod1);
  59.         t_pref1.push_back((t_pref1.back() + 1LL * t[i] * pow1[i]) % mod1);
  60.         // Hash modulo mod2 = 2^64:
  61.         s_pref2.push_back(s_pref2.back() + s[i] * pow2[i]);
  62.         t_pref2.push_back(t_pref2.back() + t[i] * pow2[i]);
  63.     }
  64.  
  65.     // Find first not equal symbol:
  66.     int f = 0;
  67.     while (f < n && s[f] == t[f]) ++f;
  68.  
  69.     std::function<std::pair<int, ull>(int,int,int)> hash_on_prefix_after_swap = [&] (const int r, const int f, const int l) {
  70.         // Function for calculating polinomial hash on substring s[0..r] after swap s[f] and s[l]
  71.         int hash1 = 0; ull hash2 = 0;
  72.         // Add hash on s[0, f);
  73.         hash1 += s_pref1[std::min(r+1, f)];
  74.         hash2 += s_pref2[std::min(r+1, f)];
  75.         if (r < f) return std::make_pair(hash1, hash2);
  76.         // Add s[l]:
  77.         hash1 = (hash1 + 1LL * s[l] * pow1[f]) % mod1;
  78.         hash2 += s[l] * pow2[f];
  79.         if (r == f) return std::make_pair(hash1, hash2);
  80.         // Add hash on s[f+1, l): 
  81.         hash1 = (0LL + hash1 + s_pref1[std::min(l, r+1)] - s_pref1[f+1] + mod1) % mod1;
  82.         hash2 += s_pref2[std::min(l, r+1)] - s_pref2[f+1];
  83.         if (r < l) return std::make_pair(hash1, hash2);
  84.         // Add s[f]:
  85.         hash1 = (hash1 + 1LL * s[f] * pow1[l]) % mod1;
  86.         hash2 += s[f] * pow2[l];
  87.         if (r == l) return std::make_pair(hash1, hash2);
  88.         // Add s[l+1, r]:
  89.         hash1 = (0LL + hash1 + s_pref1[r+1] - s_pref1[l+1] + mod1) % mod1;
  90.         hash2 += s_pref2[r+1] - s_pref2[l+1];
  91.         return std::make_pair(hash1, hash2);
  92.     };    
  93.  
  94.     // Try to change the first unequal symbol with all that stand after:
  95.     int answ = f;
  96.     for (int l = f+1; l < n; ++l) {
  97.         // Binary search: s[0..low] == t[0..low], s[0..high] != t[0..high]
  98.         int low = f-1, high = n;
  99.         while (high - low > 1) {
  100.             int mid = (low + high) / 2;
  101.             auto h1 = hash_on_prefix_after_swap(mid, f, l);
  102.             if (HASH_TYPE == SINGLE_HASH) {
  103.                 if (h1.second == t_pref2[mid+1]) {
  104.                     low = mid;
  105.                 } else {
  106.                     high = mid;
  107.                 }
  108.             } else {
  109.                 assert(HASH_TYPE == DOUBLE_HASH);
  110. 	    if (h1.first == t_pref1[mid+1] && h1.second == t_pref2[mid+1]) {
  111.                     low = mid;
  112.                 } else {
  113.                     high = mid;
  114.                 }    
  115.             }
  116.  
  117.         }
  118.         answ = std::max(answ, low+1);
  119.     }
  120.     return answ;
  121. }
  122.  
  123. void gen(std::string& s, std::string& t) {
  124. // Gen anti-hash-test against modulo 2^64
  125.     s = "a";
  126.     t = "b";
  127.     while (2 * (int)s.size() < (int)2e5) {
  128.         int n = s.size();
  129.         for (int i = 0; i < n; ++i) {
  130.             s.push_back('b' - s[i] + 'a');
  131.             t.push_back('b' - t[i] + 'a');
  132.         }
  133.     }
  134. }
  135.  
  136. int main() {
  137.     std::srand(std::time(0));
  138.     std::ios_base::sync_with_stdio(false);
  139.     std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
  140.  
  141.     int n; 
  142.     //std::cin >> n;
  143.     std::string s, t;
  144.     //std::cin >> s >> t;
  145.     gen(s,t); n = (int)s.size();
  146.     assert(s.size() == t.size());
  147.     std::cout << "Single hash answer = " << solve(s, t, SINGLE_HASH) << std::endl;
  148.     std::cout << "Double hash answer = " << solve(s, t, DOUBLE_HASH) << std::endl;
  149.     return 0; 
  150. }
Success #stdin #stdout 0.25s 12336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Single hash answer = 130048
Double hash answer = 2
https://ideone.com/bZWBhn
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!