fork(3) download 
  1. /*
  2.     Problem "Ada and Terramorphing" on spoj.com
  3.     
  4.     Solution: polynomial hash, sort, binary search, O(n log(n)^2)
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <cassert>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <random>
  12. #include <chrono>
  13. #include <string>
  14. #include <iostream>
  15.  
  16. typedef unsigned long long ull;
  17.  
  18. // Generate random base in (before, after) open interval:
  19. int gen_base(const int before, const int after) {
  20.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  21.     std::mt19937 mt_rand(seed);
  22.     int base = std::uniform_int_distribution<int>(before+2, after-1)(mt_rand);
  23.     return base % 2 == 0 ? base-1 : base;
  24. }
  25.  
  26. struct PolyHash {
  27.     // -------- Static variables --------
  28.     static const ull mod = (1ull << 61) - 1; // prime mod of polynomial hashing
  29.     static std::vector<ull> pow;             // powers of base modulo mod
  30.     static int base;                         // base (point of hashing)
  31.  
  32.     // --------- Static functons --------
  33.     static inline ull sub(ull a, ull b) { 
  34.         // Sub `b` from `a` modulo mod (0 <= a < mod, 0 <= b < mod)
  35.         return (a -= b) < 0 ? a + mod : a;
  36.     }
  37.     static inline ull add(ull a, ull b) {
  38.         // Add `b` to `a` modulo mod (0 <= a < mod, 0 <= b < mod)
  39.         return (a += b) < mod ? a : a - mod;
  40.     }
  41.  
  42.     static inline ull mul(ull a, ull b) {
  43.         // Mul `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  44.         ull l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b >> 32;
  45.         ull l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
  46.         ull ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  47.         ret = (ret & mod) + (ret>>61);
  48.         ret = (ret & mod) + (ret>>61);
  49.         return ret-1;
  50.     }
  51.  
  52.     // -------------- Variables of class -------------
  53.     std::vector<ull> pref; // Hash on prefix modulo mod
  54.  
  55.     // Cunstructor from string:
  56.     PolyHash(const std::string& s)
  57.         : pref(s.size()+1u, 0)
  58.     {
  59.         const int n = s.size(); // Firstly calculated needed power of base:
  60.         while ((int)pow.size() <= n) {
  61.             pow.push_back(mul(pow.back(), base));
  62.         }
  63.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  64.             pref[i+1] = add(mul(pref[i], base), s[i]);
  65.         }
  66.     }
  67.  
  68.     // Polynomial hash of subsequence [pos, pos+len)
  69.     inline ull operator()(const int pos, const int len) const {
  70.         return sub(pref[pos+len], mul(pow[len], pref[pos]));
  71.     }
  72. };
  73.  
  74. // Init static variables of PolyHash class:
  75. int PolyHash::base((int)1e9+7);    
  76. std::vector<ull> PolyHash::pow{1};
  77.  
  78. void gen(int n, std::string& s, std::string& t) {
  79.     s.assign(n, '?');
  80.     t.assign(n, '?');
  81.     for (int i = 0, j = n-1; i <= j; ++i, --j) {
  82.         t[j] = s[i] = 'v';
  83.     }
  84.     for (int i = 0; i < n; ++i) {
  85.         s[i] = s[i] == '?' ? '~' : s[i];
  86.         t[i] = t[i] == '?' ? '-' : t[i];
  87.     }
  88. }
  89.  
  90. void input(std::string& s, std::string& t) {
  91.     char buf[1+1000000];
  92.     scanf("%1000000s", buf);
  93.     s = buf;
  94.     scanf("%1000000s", buf);
  95.     t = buf;
  96. }
  97.  
  98. int main() {
  99.  
  100.     std::string a, b;
  101.     //input(a,b);
  102.     gen(10000, a, b);
  103.     std::cerr << "generated!" << std::endl;
  104.  
  105.     // Gen random base of hashing:
  106.     PolyHash::base = gen_base(256, 2e9);
  107.  
  108.     // Create hashing objects from strings:
  109.     PolyHash hash_a(a), hash_b(b);
  110.  
  111.     // Binary search by length of same subsequence:
  112.     int pos = -1, low = 0, high = (int)std::min(a.size(), b.size())+1;
  113.  
  114.     while (high - low > 1) {
  115.         //std::cout << "low = " << low << " high = " << high << std::endl;
  116.         int mid = (low + high) / 2;
  117.         std::vector<ull> hashes;
  118.         for (int i = 0; i + mid - 1 < (int)a.size(); ++i) {
  119.             hashes.push_back(hash_a(i,mid));
  120.         }
  121.         std::sort(hashes.begin(), hashes.end());
  122.         int p = -1;
  123.         for (int i = 0; i + mid - 1 < (int)b.size(); ++i) {
  124.             if (std::binary_search(hashes.begin(), hashes.end(), hash_b(i, mid))) {
  125.                 p = i;
  126.                 break;
  127.             }
  128.         }
  129.         if (p >= 0) {
  130.             low = mid;
  131.             pos = p;
  132.         } else {
  133.             high = mid;
  134.         }
  135.     }
  136.     assert(pos >= 0);
  137.     // Output answer:
  138.     printf("%d", low);
  139.     return 0;
  140. }
Success #stdin #stdout #stderr 0.01s 4192KB
comments (?)
stdin 
Standard input is empty
stdout 
4999
stderr 
generated!
https://ideone.com/E8YZVk
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!