fork(1) download
copy 
  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 ^ ull(new ull));
  22.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  23.     return base % 2 == 0 ? base-1 : base;
  24. }
  25.  
  26. struct PolyHash {
  27.     // -------- Static variables --------
  28.     static const int MOD = 2147483647;
  29.     static std::vector<int> pow1;        // powers of base modulo mod
  30.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  31.     static int base;                     // base (point of hashing)
  32.  
  33.     // --------- Static functons --------
  34.     static inline int sub(int a, int b) { 
  35.     	// Sub from `a` value `b` modulo mod (0 <= a < MOD, 0 <= b < MOD)
  36.         return (a -= b) < 0 ? a + MOD : a;
  37.     }
  38.  
  39.     static inline int mod(ull x) {
  40.         x = (x >> 31) + (x & MOD);
  41.         return int((x >> 31) + (x & MOD));
  42.     }
  43.  
  44.     // -------------- Variables of class -------------
  45.     std::vector<int> pref1; // Hash on prefix modulo mod
  46.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  47.  
  48.     // Cunstructor from vector:
  49.     PolyHash(const std::vector<int>& s)
  50.         : pref1(s.size()+1u, 0)
  51.         , pref2(s.size()+1u, 0)
  52.     {
  53.         while (pow1.size() <= s.size()) { // Pre-compute powers of base:
  54.             pow1.push_back(mod((ull)pow1.back() * base));
  55.             pow2.push_back(pow2.back() * base);
  56.         }
  57.         for (int i = 0; i < (int)s.size(); ++i) { // Fill arrays with polynomial hashes on prefix:
  58.             pref1[i+1] = mod(pref1[i] + (ull)s[i] * pow1[i]);
  59.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  60.         }
  61.     }
  62.  
  63.     // Polynomial hash of subsequence [pos, pos+len)
  64.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  65.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  66.         int hash1 = sub(pref1[pos+len], pref1[pos]);
  67.         ull hash2 = pref2[pos+len] - pref2[pos];
  68.         if (mxPow != 0) {
  69.             hash1 = mod((ull)hash1 * pow1[mxPow-(pos+len-1)]);
  70.             hash2 *= pow2[mxPow-(pos+len-1)];
  71.         }
  72.         return std::make_pair(hash1, hash2);
  73.     }
  74. };
  75.  
  76. // Init static variables of PolyHash class:
  77. int PolyHash::base((int)1e9+7);    
  78. std::vector<int> PolyHash::pow1{1};
  79. std::vector<ull> PolyHash::pow2{1};
  80.  
  81. void gen(int n, std::string& s, std::string& t) {
  82.     s.assign(n, '?');
  83.     t.assign(n, '?');
  84.     for (int i = 0, j = n-1; i <= j; ++i, --j) {
  85.         t[j] = s[i] = 'v';
  86.     }
  87.     for (int i = 0; i < n; ++i) {
  88.         s[i] = s[i] == '?' ? '~' : s[i];
  89.         t[i] = t[i] == '?' ? '-' : t[i];
  90.     }
  91. }
  92.  
  93. void input(std::string& s, std::string& t) {
  94.     char buf[1+1000000];
  95.     scanf("%1000000s", buf);
  96.     s = buf;
  97.     scanf("%1000000s", buf);
  98.     t = buf;
  99. }
  100.  
  101. int solve(int low, int high, const std::vector<int>& a, const std::vector<int>& b) {
  102.     high = std::min(high, std::min((int)a.size()+1, (int)b.size()+1));
  103.  
  104.     // Calculate mxPow:
  105.     const int mxPow = (int)std::max(a.size(), b.size());
  106.  
  107.     // Create hashing objects from strings:
  108.     PolyHash hash_a(a), hash_b(b);
  109.  
  110.     // Binary search by length of same subsequence:    
  111.     while (high - low > 1) {
  112.         int mid = (low + high) / 2;
  113.         std::vector<std::pair<int,ull>> hashes;
  114.         for (int i = 0; i + mid - 1 < (int)a.size(); ++i) {
  115.             hashes.push_back(hash_a(i,mid, mxPow));
  116.         }
  117.         std::sort(hashes.begin(), hashes.end());
  118.         bool success = false;
  119.         for (int i = 0; i + mid - 1 < (int)b.size(); ++i) {
  120.             if (std::binary_search(hashes.begin(), hashes.end(), hash_b(i, mid, mxPow))) {
  121.                 success = true;
  122.                 break;
  123.             }
  124.         }
  125.         if (success) {
  126.             low = mid;
  127.         } else {
  128.             high = mid;
  129.         }
  130.     }
  131.     return low;
  132. }
  133.  
  134. int code(char c) {
  135.     if (c == 'v') return 0;
  136.     if (c == '^') return 1;
  137.     if (c == '~') return 2;
  138.     assert(c == '-');
  139.     return 3;
  140. }
  141.  
  142. int main() {
  143.     // Gen random base of hashing:
  144.     PolyHash::base = gen_base(1e6, PolyHash::MOD);
  145.  
  146.     std::string a, b;
  147.     input(a,b);
  148.     //gen(1000000, a, b);
  149.  
  150.     // Convert input strings to 1-width sequences:
  151.     std::vector<int> s1(a.size()), t1(b.size());
  152.     for (int i = 0; i < (int)s1.size(); ++i) s1[i] = code(a[i]);
  153.     for (int i = 0; i < (int)t1.size(); ++i) t1[i] = code(b[i]);
  154.  
  155.     // If we can solve slow, just solve:
  156.     if (std::min(s1.size(),t1.size()) <= 2000u) {
  157.         for (auto& it : s1) it++;
  158.         for (auto& it : t1) it++;
  159.         std::cout << solve(0, (int)std::min(s1.size(),t1.size())+1, s1, t1);
  160.         return 0;
  161.     }
  162.  
  163.     // Convert input strings to 4-width sequences:
  164.     std::vector<int> s2(a.size() / 4, 1), t2(b.size() / 4, 1);
  165.     for (int i = 0; i < (int)s1.size(); ++i) {
  166.         s2[i / 4] += (s1[i] << 2 * (i % 4));
  167.     }
  168.     for (int i = 0; i < (int)t1.size(); ++i) {
  169.         t2[i / 4] += (t1[i] << 2 * (i % 4));
  170.     }
  171.  
  172.     // Get answer for 4-width sequences:
  173.     int max1 = solve(0, (int)std::min(s2.size(), t2.size())+1, s2, t2);
  174.     // Get answer for 1-width sequences:
  175.     for (auto& it : s1) it++;
  176.     for (auto& it : t1) it++;
  177.     std::cout << solve(4 * max1, 4 * max1 + 8, s1, t1);
  178.     return 0;
  179. }
Success #stdin #stdout 0s 4572KB
comments (?)
stdin
copy 
~~~vv~-~~vv~v-v--~-^-~^~-^^
~^~--v~-
stdout
copy 
4
https://ideone.com/iu3iVq
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!