Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/strings/search_rabin_karp/rolling_hash.h
Go to the documentation of this file.
00001 #ifndef H_STRINGS_SEARCH_RABIN_KARP_ROLLING_HASH
00002 #define H_STRINGS_SEARCH_RABIN_KARP_ROLLING_HASH
00003 
00007 #include "utils/preconditions/preconditions.h"
00008 namespace strings {
00009 namespace search {
00010 
00016 template <typename BaseType>
00017 class RollingHash
00018 {
00019   typedef size_t SizeType;
00020 public:
00031   RollingHash(SizeType length, BaseType modulus_, BaseType c_) {
00032     Preconditions::check(length > 0);
00033     Preconditions::check(modulus_ > 0);
00034     Preconditions::checkRange(c_, modulus_);
00035     // TODO: check for overflows!
00036     modulus = modulus_;
00037     c = c_;
00038     hash = 0;
00039     c_len = 1;
00040     // 
00041     for (SizeType i = 1; i < length; i++) {
00042       c_len = (c_len * c) % modulus;
00043     }
00044   }
00045   
00062   template <typename ValueType>
00063   inline
00064   BaseType roll(ValueType new_element, ValueType discarded_element) {
00065     hash = (modulus + hash - (discarded_element * c_len) % modulus) % modulus;
00066     hash = (hash * c) % modulus;
00067     hash = (hash + new_element) % modulus;
00068     return hash;
00069   }
00070 
00074   BaseType getHash() const {
00075     return hash;
00076   }
00077 
00078 private:
00080   BaseType modulus;
00081   
00083   BaseType c;
00084 
00086   BaseType hash;
00087 
00089   BaseType c_len;
00090 
00092   SizeType length;
00093 };
00094 
00095 } // namespace suffix_array
00096 } // namespace strings
00097 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines