fork(1) 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. // Generate random base in (before, after) open interval:
  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.     // -------- Static variables --------
  22.     static const int MOD = 2147483647;
  23.     static std::vector<int> pow1;        // powers of base modulo mod
  24.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  25.     static int base;                     // base (point of hashing)
  26.  
  27.     // --------- Static functons --------
  28.     static inline int diff(int a, int b) { 
  29.     	// Diff between `a` and `b` modulo 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;
  35.         x = (x >> 31) + (x & MOD);
  36.         return int((x >> 31) + (x & MOD));
  37.     }
  38.  
  39.     // -------------- Variables of class -------------
  40.     std::vector<int> pref1; // Hash on prefix modulo mod
  41.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  42.  
  43.     // Cunstructor from string:
  44.     PolyHash(const std::string& s)
  45.         : pref1(s.size()+1u, 0)
  46.         , pref2(s.size()+1u, 0)
  47.     {
  48.         while (pow1.size() <= s.size()) { // Pre-compute powers of base:
  49.             pow1.push_back(mod((ull)pow1.back() * base));
  50.             pow2.push_back(pow2.back() * base);
  51.         }
  52.         for (int i = 0; i < (int)s.size(); ++i) { // Fill arrays with polynomial hashes on prefix:
  53.             pref1[i+1] = mod(pref1[i] + (ull)s[i] * pow1[i]);
  54.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  55.         }
  56.     }
  57.  
  58.     // Polynomial hash of subsequence [pos, pos+len)
  59.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  60.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  61.         int hash1 = diff(pref1[pos+len], pref1[pos]);
  62.         ull hash2 = pref2[pos+len] - pref2[pos];
  63.         if (mxPow != 0) {
  64.             hash1 = mod((ull)hash1 * pow1[mxPow-(pos+len-1)]);
  65.             hash2 *= pow2[mxPow-(pos+len-1)];
  66.         }
  67.         return std::make_pair(hash1, hash2);
  68.     }
  69.  
  70.     // Polynomial hash on prefix [0, len) after swap items i and j (chars ci and cj):
  71.     inline std::pair<int, ull> prefix_after_swap(const int len, const int i, const int j, const char ci, const char cj) const {
  72.         // Prefix before i:
  73.         int hash1 = pref1[std::min(len, i)];
  74.         ull hash2 = pref2[std::min(len, i)];
  75.         if (len <= i) return std::make_pair(hash1, hash2);
  76.         // Add symbol on position i after swap:
  77.         hash1 = mod(hash1 + (ull)cj * pow1[i]);
  78.         hash2 += cj * pow2[i];
  79.         // Prefix prefore j:
  80.         hash1 = mod(hash1 + (ull)diff(pref1[std::min(len, j)], pref1[i+1]));
  81.         hash2 += pref2[std::min(len,j)] - pref2[i+1];
  82.         if (len <= j) return std::make_pair(hash1, hash2);
  83.         // Add symbol on position j after swap:
  84.         hash1 = mod(hash1 + (ull)ci * pow1[j]);
  85.         hash2 += ci * pow2[j];
  86.         // Prefix before len:
  87.         hash1 = mod(hash1 + (ull)diff(pref1[len], pref1[j+1]));
  88.         hash2 += pref2[len] - pref2[j+1];
  89.         return std::make_pair(hash1, hash2);
  90.     }
  91. };
  92.  
  93. // Init static variables of PolyHash class:
  94. int PolyHash::base((int)1e9+7);    
  95. std::vector<int> PolyHash::pow1{1};
  96. std::vector<ull> PolyHash::pow2{1};
  97.  
  98. int solve(const int n, const std::string& s, const std::string& t) {
  99.     // Gen random base of hashing:
  100.     PolyHash::base = gen_base(256, PolyHash::MOD);
  101.  
  102.     // Construct polynomial hashes on prefixes of strings s and t:
  103.     PolyHash hash_s(s), hash_t(t);
  104.  
  105.     // Find first not-equal symbol:
  106.     int pos1 = 0;
  107.     while (pos1 < n && s[pos1] == t[pos1]) ++pos1;
  108.  
  109.     // Try to swap pos1 with everything symbol after and use binary search for finding LCP:
  110.     int answ = pos1;
  111.     for (int pos2 = pos1+1; pos2 < n; ++pos2) {
  112.         // Binary search:
  113.         int low = 0, high = n+1;
  114.         while (high-low > 1) {
  115.             const int mid = (low + high) / 2;
  116.             const auto hs = hash_s.prefix_after_swap(mid, pos1, pos2, s[pos1], s[pos2]);
  117.             if (hs == hash_t(0, mid)) {
  118.                 low = mid;
  119.             } else {
  120.                 high = mid;
  121.             }
  122.         }
  123.         // Update answer:
  124.         answ = std::max(answ, low);
  125.     }
  126.     return answ;
  127. }
  128.  
  129. int main() {
  130.     // Input:
  131.     int n;
  132.     scanf("%d", &n);
  133.     char buf[1+200000];
  134.     scanf("%200000s", buf);
  135.     std::string s(buf);
  136.     scanf("%200000s", buf);
  137.     std::string t(buf);
  138.     // Solve and output:
  139.     printf("%d", solve(n,s,t));
  140.     return 0;
  141. }
Success #stdin #stdout 0s 4204KB
comments (?)
stdin
copy 
10
aaabaaaaaa
aaaaaaaaab
stdout
copy 
10
https://ideone.com/p4kzu9
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!