Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

SequenceHash

By: a guest on Jun 22nd, 2012  |  syntax: C++  |  size: 1.03 KB  |  views: 344  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2.  * Author : Nikhil Garg
  3.  * Date   : 2011-12-29
  4.  * A SequenceHash data structure.
  5.  * Initial construction takes O(N) time.
  6.  * After that it can query hashcode of any contiguous subsequence in O(1)
  7.  *
  8.  */
  9.  
  10. struct SequenceHash
  11. {
  12.     vector<long long> prefixHash, powers;
  13.    
  14.     SequenceHash(const vector<int>& seq)
  15.     {
  16.         int L = seq.size();
  17.         prefixHash.resize(L+1); powers.resize(L+1);
  18.         prefixHash[0] = 0LL;    powers[0] = 1LL;
  19.        
  20.         for(int i = 1; i <= L;i++)
  21.         {
  22.             prefixHash[i] = prefixHash[i-1] * 31LL + seq[i-1];
  23.             powers[i] = powers[i-1] * 31LL;
  24.         }        
  25.     }
  26.    
  27.     long long hash(int a, int b)           // Returns hash code for seq[a..b], both endpoints inclusive
  28.     {
  29.         return prefixHash[b+1] - prefixHash[a] * powers[b-a+1];
  30.     }
  31. };
  32.  
  33.  
  34. int main()
  35. {
  36.    //Example usage
  37.     int A[] = { 1, 2, 3, 1, 2, 3};
  38.     SequenceHash sh(VI(A));             // Just instantiate the SequenceHash
  39.     assert( sh.hash(0,2) == sh.hash(3,5));
  40. }