Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- static const long MOD = 1e11+19;
- static const int BASE = 101;
- public:
- int rolling_hash(vector<int>& A, vector<int>& B, int size) {
- long long hashA=0, hashB=0, power=1;
- unordered_set<long> seen;
- // Get all hash for A of length size.
- for(int i=0; i<size; i++){
- hashA = hashA*BASE + A[i];
- hashA %= MOD;
- }
- for(int i=0;i<size-1;i++)
- power = (power*BASE)%MOD;
- seen.insert(hashA);
- for(int i=size; i<A.size(); i++){
- hashA = (((hashA-power*A[i-size])%MOD)+MOD)%MOD;
- hashA = (hashA*BASE+A[i])%MOD;
- seen.insert(hashA);
- }
- // Iterate over all hashes of B and check if it exists in hashset of A.
- for(int i=0; i<size; i++)
- hashB = (hashB*BASE+B[i])%MOD;
- if(seen.count(hashB))
- return true;
- for(int i=size; i<B.size(); i++){
- hashB = (((hashB-power*B[i-size])%MOD)+MOD)%MOD;
- hashB = (hashB*BASE+B[i])%MOD;
- if(seen.count(hashB))
- return true;
- }
- return false;
- }
- int findLength(vector<int>& A, vector<int>& B){
- int start=1, end=min(A.size(), B.size())+1;
- // Find rightmost using binary search.
- while(start<end){
- int mid = (start+end)/2;
- if(!rolling_hash(A, B, mid))
- end = mid;
- else
- start = mid+1;
- }
- return end-1;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement