fork(5) download
copy 
  1. /*
  2.     Задача "1517. Свобода выбора" с сайта acm.timus.ru
  3.     
  4.     Решение: полиномиальный хэш, сортировка, бинарный поиск 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.  
  15. typedef unsigned long long ull;
  16.  
  17. // Генерация случайного основания хэширования на отрезке (before, after):
  18. int gen_base(const int before, const int after) {
  19.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  20.     std::mt19937 mt_rand(seed);
  21.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  22.     return base % 2 == 0 ? base-1 : base;
  23. }
  24.  
  25. struct PolyHash {
  26.     // -------- Статические переменные класса --------
  27.     static const int mod = (int)1e9+123; // простой модуль полиномиального хэширования
  28.     static std::vector<int> pow1;        // степени основания base по модулю mod
  29.     static std::vector<ull> pow2;        // степени основания base по модулю 2^64
  30.     static int base;                     // основание base
  31.  
  32.     // --------- Статические функции класса ---------
  33.     static inline int diff(int a, int b) { // разность a и b по модуль mod (Предполагается: 0 <= a < mod, 0 <= b < mod)
  34.         return (a -= b) < 0 ? a + mod : a;
  35.     }
  36.  
  37.     // -------------- Переменные класса -------------
  38.     std::vector<int> pref1; // Полиномиальный хэш на префиксе по модулю mod
  39.     std::vector<ull> pref2; // Полиномиальный хэш на префиксе по модулю 2^64
  40.  
  41.     // Конструктор от строки:
  42.     PolyHash(const std::string& s)
  43.         : pref1(s.size()+1u, 0)
  44.         , pref2(s.size()+1u, 0)
  45.     {
  46.         assert(base < mod);
  47.         const int n = s.size(); // Досчитываем необходимые степени основания по модулям хэширования
  48.         while ((int)pow1.size() <= n) {
  49.             pow1.push_back(1LL * pow1.back() * base % mod);
  50.             pow2.push_back(pow2.back() * base);
  51.         }
  52.         for (int i = 0; i < n; ++i) { // Заполняем массив полиномиальных хэшей на префиксе
  53.             assert(base > s[i]);
  54.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  55.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  56.         }
  57.     }
  58.  
  59.     // Полиномиальный хэш подпоследовательности [pos, pos+len)
  60.     // Если mxPow != 0, то происходит домножение значения до старшей степени base ^ mxPow
  61.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  62.         int hash1 = pref1[pos+len] - pref1[pos];
  63.         ull hash2 = pref2[pos+len] - pref2[pos];
  64.         if (hash1 < 0) hash1 += mod;
  65.         if (mxPow != 0) {
  66.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  67.             hash2 *= pow2[mxPow-(pos+len-1)];
  68.         }
  69.         return std::make_pair(hash1, hash2);
  70.     }
  71. };
  72.  
  73. // Инициализация статических объектов класса PolyHash:
  74. int PolyHash::base((int)1e9+7);    
  75. std::vector<int> PolyHash::pow1{1};
  76. std::vector<ull> PolyHash::pow2{1};
  77.  
  78. int main() {
  79.     // Чтение данных:
  80.     int n;
  81.     scanf("%d", &n);
  82.     char buf[1+100000];
  83.     scanf("%100000s", buf);
  84.     std::string a(buf);
  85.     scanf("%100000s", buf);
  86.     std::string b(buf);
  87.  
  88.     // Вычисление максимальной степени:
  89.     const int mxPow = std::max((int)a.size(), (int)b.size());
  90.  
  91.     // Генерация случайного основания хэширования:
  92.     PolyHash::base = gen_base(256, PolyHash::mod);
  93.  
  94.     // Создание объектов хэширования:
  95.     PolyHash hash_a(a), hash_b(b);
  96.  
  97.     // Бинарный поиск по длине общей подстроки:
  98.     int pos = -1, low = 0, high = std::min(a.size(), b.size())+1;
  99.     while (high - low > 1) {
  100.         int mid = (low + high) / 2;
  101.         std::vector<std::pair<int,ull>> hashes;
  102.         for (int i = 0; i + mid <= n; ++i) {
  103.             hashes.push_back(hash_a(i,mid,mxPow));
  104.         }
  105.         std::sort(hashes.begin(), hashes.end());
  106.         int p = -1;
  107.         for (int i = 0; i + mid <= n; ++i) {
  108.             if (std::binary_search(hashes.begin(), hashes.end(), hash_b(i, mid, mxPow))) {
  109.                 p = i;
  110.                 break;
  111.             }
  112.         }
  113.         if (p >= 0) {
  114.             low = mid;
  115.             pos = p;
  116.         } else {
  117.             high = mid;
  118.         }
  119.     }
  120.     assert(pos >= 0);
  121.     // Вывод ответа:        
  122.     printf("%s", b.substr(pos, low).c_str());
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
28
VOTEFORTHEGREATALBANIAFORYOU
CHOOSETHEGREATALBANIANFUTURE
stdout
copy 
THEGREATALBANIA
https://ideone.com/vR2WL3
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!