Advertisement
nikunjsoni

718

May 21st, 2021
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. class Solution {
  2. static const long MOD = 1e11+19;
  3. static const int BASE = 101;
  4. public:
  5.     int rolling_hash(vector<int>& A, vector<int>& B, int size) {
  6.         long long hashA=0, hashB=0, power=1;
  7.         unordered_set<long> seen;
  8.        
  9.         // Get all hash for A of length size.
  10.         for(int i=0; i<size; i++){
  11.             hashA = hashA*BASE + A[i];
  12.             hashA %= MOD;
  13.         }
  14.         for(int i=0;i<size-1;i++)
  15.             power = (power*BASE)%MOD;
  16.         seen.insert(hashA);
  17.        
  18.         for(int i=size; i<A.size(); i++){
  19.             hashA = (((hashA-power*A[i-size])%MOD)+MOD)%MOD;
  20.             hashA = (hashA*BASE+A[i])%MOD;
  21.             seen.insert(hashA);
  22.         }
  23.        
  24.         // Iterate over all hashes of B and check if it exists in hashset of A.
  25.         for(int i=0; i<size; i++)
  26.             hashB = (hashB*BASE+B[i])%MOD;
  27.            
  28.         if(seen.count(hashB))
  29.             return true;
  30.        
  31.         for(int i=size; i<B.size(); i++){
  32.             hashB = (((hashB-power*B[i-size])%MOD)+MOD)%MOD;
  33.             hashB = (hashB*BASE+B[i])%MOD;
  34.             if(seen.count(hashB))
  35.                 return true;
  36.         }    
  37.         return false;
  38.     }
  39.    
  40.     int findLength(vector<int>& A, vector<int>& B){
  41.         int start=1, end=min(A.size(), B.size())+1;
  42.         // Find rightmost using binary search.
  43.         while(start<end){
  44.             int mid = (start+end)/2;
  45.             if(!rolling_hash(A, B, mid))
  46.                 end = mid;
  47.             else
  48.                 start = mid+1;
  49.         }
  50.         return end-1;
  51.     }
  52. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement