fork(4) download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<list>
  4. #include<map>
  5. #include<set>
  6. #include<functional>
  7. #include<algorithm>
  8. #include<cassert>
  9. #include<iterator>
  10.  
  11. using namespace std;
  12.  
  13. using Ull = unsigned long long;
  14. using HashPair = pair<Ull, long long>;
  15.  
  16. const long long MOD = 1000*1000*1000 + 7;
  17. const Ull MUL = 5;
  18.  
  19. struct Hash
  20. {
  21.     vector<Ull> pow64, hash64;
  22.     vector<long long> powP, hashP;
  23.     Hash(const string & s = "") :  pow64(s.size()+1), hash64(s.size()+1),
  24.                                        powP(s.size()+1), hashP(s.size()+1)
  25.     {
  26.         hashP[0] = 0;
  27.         hash64[0] = 0;
  28.         powP[0] = 1;
  29.         pow64[0] = 1;
  30.         for(int i = 0; i<(int)s.size(); i++)
  31.         {
  32.             int c;
  33.             switch(s[i]){
  34.                 case '-' : c = 1; break;
  35.                 case '~' : c = 2; break;
  36.                 case 'v' : c = 3; break;
  37.                 default : c  = 4;
  38.             }
  39.             hash64[i+1] = hash64[i]*MUL + c;
  40.             hashP[i+1] = (hashP[i]*MUL + c)%MOD;
  41.             pow64[i+1] = pow64[i]*MUL;
  42.             powP[i+1] = (powP[i]*MUL)%MOD;
  43.         }
  44.     }
  45.  
  46.     long long getHashP(int l, int r)
  47.     {
  48.         long long tmp = (hashP[r] - hashP[l-1]*powP[r-l+1])%MOD;
  49.         return tmp + (tmp<0?MOD:0);
  50.     }
  51.  
  52.     Ull getHash64(int l, int r)
  53.     {
  54.         return hash64[r] - hash64[l-1]*pow64[r-l+1];
  55.     }
  56.  
  57.     HashPair getHash(int l, int r)
  58.     {
  59.         if(l>r)
  60.             return {0,0};
  61.         return {getHash64(l,r), getHashP(l,r)};
  62.     }
  63. };
  64.  
  65.  
  66. struct OpenAddressHashTable
  67. {
  68.     static const int size{4*1000*1000 + 37}; //prime number greater than 4'000'000
  69.     static const int step{50000};
  70.     HashPair cleared{make_pair(0ULL, -1LL)};
  71.  
  72.     vector<HashPair> a{size, cleared};
  73.  
  74.     int hash(const HashPair &toHash) const {
  75.     	return int((toHash.first + (Ull)toHash.second)%size);
  76.     }
  77.  
  78.     int hash2(const HashPair &toHash) const {
  79.     	return int((toHash.first + (Ull)toHash.second)%step) + 1;
  80.     }
  81.  
  82.     void clear()
  83.     {
  84.         a.assign(size, cleared);
  85.     }
  86.  
  87.     void insert(const HashPair & toInsert)
  88.     {
  89.     	int first = hash(toInsert);
  90.         int i = first;
  91.         int realStep = -1;
  92.         while (true)
  93.         {
  94.             if(a[i] == cleared)
  95.             {
  96.                 a[i] = toInsert;
  97.                 return;
  98.             }
  99.             if(a[i] == toInsert)
  100.                 return;
  101.  
  102.             if (realStep == -1) {
  103.             	realStep = hash2(toInsert);
  104.             }
  105.             i+=realStep;
  106.             if (i >= size) {
  107.             	i -= size;
  108.             }
  109.             assert(i!=first && "NO PLACE");
  110.         }
  111.     }
  112.  
  113.     int count(const HashPair & toFind)
  114.     {
  115.     	int first = hash(toFind);
  116.         int i = first;
  117.         int realStep = -1;
  118.         while (true)
  119.         {
  120.             if(a[i] == cleared)
  121.             {
  122.                 return 0;
  123.             }
  124.             if(a[i] == toFind)
  125.                 return 1;
  126.             if (realStep == -1) {
  127.             	realStep = hash2(toFind);
  128.             }
  129.             i+=realStep;
  130.             if (i >= size) {
  131.             	i -= size;
  132.             }
  133.             assert(i!=first && "NO PLACE");
  134.         }
  135.     }
  136.  
  137. };
  138.  
  139. struct Buckets
  140. {
  141.     vector<int> beginnings;
  142.     vector<int> next;
  143.     vector<HashPair> mem;
  144.     int firstUnused{0};
  145.  
  146.     Buckets(int cnt, int capacity) : beginnings(cnt, -1), next(capacity, -1), mem(capacity){}
  147.  
  148.     void clear()
  149.     {
  150.         beginnings.assign(beginnings.size(), -1);
  151.         firstUnused = 0;
  152.     }
  153.  
  154.     void push_back(int bucket, const HashPair & toPush)
  155.     {
  156.         mem[firstUnused] = toPush;
  157.         next[firstUnused] = beginnings[bucket];
  158.         beginnings[bucket] = firstUnused++;
  159.     }
  160.  
  161.     struct Iterator : iterator<std::forward_iterator_tag, HashPair>
  162.     {
  163.         Buckets & src;
  164.         int pos;
  165.         Iterator(Buckets & src, int pos = -1) : src(src), pos(pos){};
  166.  
  167.         Iterator & operator ++ ()
  168.         {
  169.             pos = src.next[pos];
  170.             return *this;
  171.         }
  172.         HashPair & operator *()
  173.         {
  174.             return src.mem[pos];
  175.         }
  176.         bool operator == (const Iterator & a)
  177.         {
  178.             return (&src == &a.src) && (pos == a.pos);
  179.         }
  180.         bool operator != (const Iterator & a)
  181.         {
  182.             return (&src != &a.src) || (pos != a.pos);
  183.         }
  184.     };
  185.  
  186.     Iterator getBegin(int bucket)
  187.     {
  188.         return Iterator(*this, beginnings[bucket]);
  189.     }
  190.     Iterator getEnd()
  191.     {
  192.         return Iterator(*this);
  193.     }
  194. };
  195.  
  196. struct SeparateChainingHashTable
  197. {
  198.     static const int bucketsCnt{7*1000*1000};
  199.     static const int size{1000*1000 + 5};
  200.  
  201.     Buckets a{bucketsCnt, size};
  202.     int hash(const HashPair &toHash) const
  203.     {
  204.     	return int((toHash.first + (Ull)toHash.second)%bucketsCnt);
  205.     }
  206.  
  207.     void clear()
  208.     {
  209.         a.clear();
  210.     }
  211.  
  212.     void insert(const HashPair & toInsert)
  213.     {
  214.         int hashed = hash(toInsert);
  215.         if(!any_of(a.getBegin(hashed), a.getEnd(),
  216.                    [toInsert](const HashPair & toCheck){return toInsert == toCheck;} ))
  217.         {
  218.             a.push_back(hashed, toInsert);
  219.         }
  220.     }
  221.  
  222.     int count(const HashPair & toFind)
  223.     {
  224.         int hashed = hash(toFind);
  225.         return any_of(a.getBegin(hashed), a.getEnd(),
  226.                    [toFind](const HashPair & toCheck){return toFind == toCheck;} );
  227.     }
  228.  
  229. };
  230.  
  231. void gen_test(int n, std::string& A, std::string& B) {
  232. 	A.assign(n, 'v');
  233. 	B.assign(n, 'v');
  234. 	for (int i = 0, j = n-1; i <= j; ++i,--j) {
  235. 		A[i] = '~';
  236. 		B[j] = '-';
  237. 	}
  238. }
  239.  
  240. int main()
  241. {
  242.     ios::sync_with_stdio(false);
  243.     cin.tie(nullptr);
  244.  
  245.     string A, B;
  246.  
  247.     //cin >> A;
  248.     //cin >> B;
  249.     gen_test(1000000, A, B);
  250.     int lLen = 0, rLen = min(A.size(), B.size()) + 1;
  251.  
  252.  
  253.     Hash hashA(A), hashB(B);
  254.     SeparateChainingHashTable hashes;
  255.  
  256.     while(lLen+1<rLen)
  257.     {
  258.         int mid = (lLen+rLen)/2;
  259.  
  260.         hashes.clear();
  261.         for(int i = 0; i+mid <= (int)A.size(); i++)
  262.             hashes.insert(hashA.getHash(i+1, i+mid));
  263.  
  264.         bool noThatHash = 1;
  265.         for(int i = 0; i + mid <= (int)B.size() && noThatHash; i++)
  266.         {
  267.             noThatHash = !hashes.count(hashB.getHash(i+1,i+mid));
  268.         }
  269.  
  270.         if(noThatHash)
  271.             rLen = mid;
  272.         else
  273.             lLen = mid;
  274.     }
  275.     cout << lLen << endl;
  276.  
  277.  
  278.     return 0;
  279. }
  280.  
Success #stdin #stdout 0.8s 114112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
500000
https://ideone.com/AcLnjq
language:
C++14 (gcc 8.3)
created:
6 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!