Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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