fork(9) download
copy 
  1. #include <stdio.h>
  2. #include <string>
  3. #include <vector>
  4. #include <random>
  5. #include <chrono>
  6. #include <array>
  7. #include <iostream>
  8. #include <algorithm>
  9.  
  10. typedef unsigned long long ull;
  11.  
  12. int gen_base(int before, int after) {
  13.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  14.     std::mt19937 gen(seed ^ ull(new ull));
  15.     std::uniform_int_distribution<int> dist(before+2, after-1);
  16.     int base = dist(gen);
  17.     return base % 2 == 0 ? base - 1 : base;
  18. }
  19.  
  20. struct HashTable {
  21.  
  22.     static const int mod = 2000177; // 2000177, 3000077, 4000277
  23.  
  24.     const int step;
  25.  
  26.     std::array<ull, mod> data;
  27.  
  28.     inline int get_hash(ull value) const {
  29.         return int((value + step) % mod);
  30.     }
  31.  
  32.     HashTable() : step(gen_base(mod / 10, mod)) {
  33.         for (auto& it : data) it = 0;
  34.     }
  35.  
  36.     void insert(ull value) {
  37.         int hash = get_hash(value);
  38.         while (true) {
  39.             if (data[hash] == value) {
  40.                 return;
  41.             }
  42.             if (data[hash] == 0) {
  43.                 data[hash] = value;
  44.                 return;
  45.             }
  46.             hash += step;
  47.             if (hash >= mod) {
  48.                 hash -= mod;
  49.             }
  50.         }
  51.     }
  52.  
  53.     bool search(ull value) const {
  54.         int hash = get_hash(value);
  55.         while (true) {
  56.             if (data[hash] == value) {
  57.                 return true;
  58.             }
  59.             if (data[hash] == 0) {
  60.                 break;
  61.             }
  62.             hash += step;
  63.             if (hash >= mod) {
  64.                 hash -= mod;
  65.             }
  66.         }
  67.         return false;
  68.     }    
  69. };
  70.  
  71. struct PolyHash {
  72.     // -------- Static variables --------
  73.     static const ull mod = (ull(1) << 61) - 1; // prime mod of hashing
  74.     static int base;                           // odd base of hashing
  75.     static std::vector<ull> pow;               // powers of base modulo mod;
  76.  
  77.     // -------- Static functions --------
  78.     static inline ull add(ull a, ull b) {
  79.         // Calculate (a + b) % mod, 0 <= a < mod, 0 <= b < mod
  80.         return (a += b) < mod ? a : a - mod;
  81.     }
  82.  
  83.     static inline ull sub(ull a, ull b) {
  84.         // Calculate (a - b) % mod, 0 <= a < mod, 0 <= b < mod
  85.         return (a -= b) < mod ? a : a + mod;
  86.     }
  87.  
  88.     static inline ull mul(ull a, ull b){
  89.         // Calculate (a * b) % mod, 0 <= a < mod, 0 <= b < mod
  90.         ull l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
  91.         ull l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
  92.         ull ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  93.         ret = (ret & mod) + (ret >> 61);
  94.         ret = (ret & mod) + (ret >> 61);
  95.         return ret-1;
  96.     }
  97.  
  98.     // -------- Variables of class --------
  99.     std::vector<ull> pref; // polynomial hash on prefix
  100.  
  101.     // Constructor from string:
  102.     PolyHash(const std::string& s) 
  103.         : pref(s.size()+1u, 0) 
  104.     {
  105.         // Pre-calculate powers of base:
  106.         while (pow.size() <= s.size()) {
  107.             pow.push_back(mul(pow.back(), base));
  108.         }
  109.         // Calculate polinomial hash on prefix:
  110.         for (int i = 0; i < (int)s.size(); ++i) {
  111.             pref[i+1] = add(mul(pref[i], base), s[i]);
  112.         }
  113.     }
  114.  
  115.     // Get hash from [pos, pos+len-1] segment of string
  116.     inline ull operator()(const int pos, const int len) const {
  117.         return sub(pref[pos+len], mul(pref[pos], pow[len]));
  118.     }
  119.  
  120. };
  121.  
  122. // Init static variables of class PolyHash:
  123. int PolyHash::base((int)1e9+7);
  124. std::vector<ull> PolyHash::pow{1};
  125.  
  126. // Solve problem using binary search and hash table in O(n log(n)):
  127. int solve(const std::string& s, const std::string& t) {    
  128.     // Pre-calculate hash:
  129.     PolyHash hash_s(s), hash_t(t);
  130.     // Binary search by len:
  131.     int low = 0, high = std::min((int)s.size(), (int)t.size())+1;
  132.     while (high - low > 1) {
  133.         int mid = (low + high) / 2;
  134.         // Insert all hashes of segments length mid of string s:
  135.         HashTable hashes;
  136.         for (int i = 0; i + mid - 1 < (int)s.size(); ++i) {
  137.             hashes.insert(hash_s(i, mid));
  138.         }
  139.         // Search all hashes of segments length mid of string t:
  140.         bool success = false;
  141.         for (int i = 0; i + mid - 1 < (int)t.size(); ++i) {
  142.             if (hashes.search(hash_t(i, mid))) {
  143.                 success = true;
  144.                 break;
  145.             }
  146.         }
  147.         if (success) low = mid; else high = mid;
  148.     }
  149.     return low;
  150. }
  151.  
  152. void input(std::string& a, std::string& b) {
  153.     char buf[1+1000000];
  154.     scanf("%1000000s", buf);
  155.     a = buf;
  156.     scanf("%1000000s", buf);
  157.     b = buf;
  158. }
  159.  
  160. void gen(const int n, std::string& s, std::string& t) {
  161. // Generate test length n and answer n / 2
  162.     s.assign(n, 'v');
  163.     t.assign(n, 'v');
  164.     for (int i = 0, j = n-1; i <= j; ++i, --j) {
  165.         s[i] = '~';
  166.         t[j] = '-';
  167.     }
  168. }
  169.  
  170. int main() {
  171.     // Generate random base:
  172.     PolyHash::base = gen_base(256, 2e9);
  173.     std::string s, t;
  174.     input(s, t);
  175.     std::cout << solve(s,t);
  176.     return 0;
  177. }
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ACmWDq
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!