Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Author : Nikhil Garg
- * Date : 2011-12-29
- * A SequenceHash data structure.
- * Initial construction takes O(N) time.
- * After that it can query hashcode of any contiguous subsequence in O(1)
- *
- */
- struct SequenceHash
- {
- vector<long long> prefixHash, powers;
- SequenceHash(const vector<int>& seq)
- {
- int L = seq.size();
- prefixHash.resize(L+1); powers.resize(L+1);
- prefixHash[0] = 0LL; powers[0] = 1LL;
- for(int i = 1; i <= L;i++)
- {
- prefixHash[i] = prefixHash[i-1] * 31LL + seq[i-1];
- powers[i] = powers[i-1] * 31LL;
- }
- }
- long long hash(int a, int b) // Returns hash code for seq[a..b], both endpoints inclusive
- {
- return prefixHash[b+1] - prefixHash[a] * powers[b-a+1];
- }
- };
- int main()
- {
- //Example usage
- int A[] = { 1, 2, 3, 1, 2, 3};
- SequenceHash sh(VI(A)); // Just instantiate the SequenceHash
- assert( sh.hash(0,2) == sh.hash(3,5));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement