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.  
  52.     for(int N = 100; N <= 100000000; N *= 10)
  53.     {
  54.         vector<int>   a;
  55.         vector<short> b;
  56.  
  57.         for(int i = 0; i < N; ++i)
  58.         {
  59.             a.push_back( 1 );
  60.             if (i&1)
  61.                 b.push_back(1);
  62.         }
  63.         b.push_back(0);
  64.  
  65.         auto start = clock();
  66.         cout << "N : " << N << endl;
  67.         cout << (search(a.begin(),a.end(),b.begin(),b.end()) != a.end()) << endl;
  68.         auto stop = clock();
  69.         auto rand_time = stop - start;
  70.         cout << "search: " << rand_time << endl;
  71.         start = clock();
  72.  
  73.         cout << find(a,b) << endl;
  74.         stop = clock();
  75.         rand_time = stop - start;
  76.         cout << "find  : " << rand_time << endl << endl;
  77.     }
  78.  
  79. }
  80.  
Time limit exceeded #stdin #stdout 5s 8592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N : 100
0
search: 51
0
find  : 28

N : 1000
0
search: 452
0
find  : 189

N : 10000
0
search: 43831
0
find  : 1780

N : 100000
0
search: 4410059
0
find  : 19123

N : 1000000
https://ideone.com/NS1lES
language:
C++14 (gcc 8.3)
created:
7 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!