fork download
copy 
  1. #include <vector>
  2. #include <string>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <algorithm>
  6. #include <random>
  7. #include <chrono>
  8.  
  9. using namespace std;
  10.  
  11. typedef unsigned long long ull;
  12. typedef pair<ull,ull> pll;
  13.  
  14. const ull base = 31;
  15. const pll mod = pll(100000000013,1000000000009);
  16.  
  17. template <typename T>
  18. void modif(pll& value, T add){
  19.     value = pll( (value.first * base + add) % mod.first, (value.second* base + add) % mod.second);
  20. }
  21.  
  22. template < typename LeftOperand, typename RigthOperand >
  23. LeftOperand * find(vector<LeftOperand>& left, vector<RigthOperand>& rigth){
  24.      if (rigth.size() > left.size())
  25.         return nullptr;
  26.  
  27.      pll powMod = pll(1,1);
  28.      pll currentLeft = pll(0,0);
  29.      pll valueRigth = pll(0,0);
  30.  
  31.      for (size_t i =0; i < rigth.size(); i++ ) {
  32.           modif(powMod,0);
  33.           modif(currentLeft, left[i]);
  34.           modif(valueRigth, rigth[i]);
  35.      }
  36.      for (size_t L = 0, R = rigth.size(); ;L++,R++){
  37.             if (currentLeft == valueRigth)
  38.                 return &left[L];
  39.             if (R == left.size())
  40.                 return nullptr;
  41.             modif(currentLeft, left[R]);
  42.             currentLeft = pll( 
  43.                 (currentLeft.first - left[L]*powMod.first % mod.first ) % mod.first,
  44.                 (currentLeft.second- left[L]*powMod.second% mod.second) % mod.second
  45.             );
  46.      }
  47. }
  48.  
  49. int main()
  50. {
  51.     default_random_engine dre{random_device()()};
  52.     uniform_int_distribution<> uid(0,1000);
  53.  
  54.     for(int N = 100; N <= 100000000; N *= 100)
  55.     {
  56.         vector<int>   a;
  57.         vector<short> b;
  58.  
  59.         for(int i = 0; i < N; ++i)
  60.         {
  61.             a.push_back(uid(dre));
  62.             if (N%10 == 0)
  63.                 b.push_back(uid(dre));
  64.         }
  65.  
  66.         auto start = chrono::high_resolution_clock::now();
  67.         cout << "N : " << N << "  " <<(search(a.begin(),a.end(),b.begin(),b.end()) != a.end()) << endl;
  68.         auto stop = chrono::high_resolution_clock::now();
  69.         auto rand_time = stop - start;
  70.         cout << "search: " << chrono::duration_cast<chrono::nanoseconds>(stop-start).count() << endl;
  71.         start = chrono::high_resolution_clock::now();
  72.         cout << find(a,b) << endl;;
  73.         stop = chrono::high_resolution_clock::now();
  74.         rand_time = stop - start;
  75.         cout << "find  : " << chrono::duration_cast<chrono::nanoseconds>(stop-start).count() << endl << endl;
  76.     }
  77.  
  78. }
  79.  
Time limit exceeded #stdin #stdout 5s 396672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N : 100  0
search: 67937
0
find  : 39453

N : 10000  0
search: 23288
0
find  : 2447350

N : 1000000  0
search: 1626736
0
find  : 242791152
https://ideone.com/V5WDTS
language:
C++14 (gcc 8.3)
created:
7 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!