Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <rolling_hash.h>
Public Member Functions | |
RollingHash (SizeType length, BaseType modulus_, BaseType c_) | |
template<typename ValueType > | |
BaseType | roll (ValueType new_element, ValueType discarded_element) |
BaseType | getHash () const |
Private Types | |
typedef size_t | SizeType |
Private Attributes | |
BaseType | modulus |
BaseType | c |
BaseType | hash |
BaseType | c_len |
SizeType | length |
Rolling hash implementation -- can efficiently compute hash of sequence of fixed length.
typedef size_t strings::search::RollingHash< BaseType >::SizeType [private] |
strings::search::RollingHash< BaseType >::RollingHash | ( | SizeType | length, |
BaseType | modulus_, | ||
BaseType | c_ | ||
) | [inline] |
Create rolling hash and initialize it to zero sequence.
The rolling hash value is defined as hash = sum_{i=0}^{length-1} seq[i] * c_^(length-1-i) mod modulus_
length | length of the sequence |
modulus_ | modulus is best to be a prime |
c_ |
BaseType strings::search::RollingHash< BaseType >::getHash | ( | ) | const [inline] |
BaseType strings::search::RollingHash< BaseType >::roll | ( | ValueType | new_element, |
ValueType | discarded_element | ||
) | [inline] |
Moves the hashing function window by one character
Note: This implementation is very conservative in considering overflows. If you know about your data limitations, it can be probably optimized to two multiplications and one modular division.
new_element | new element of the sequence |
discarded_element | element of the sequence which "fell out" |
BaseType strings::search::RollingHash< BaseType >::c [private] |
TODO
BaseType strings::search::RollingHash< BaseType >::c_len [private] |
value
BaseType strings::search::RollingHash< BaseType >::hash [private] |
current value of the hash
SizeType strings::search::RollingHash< BaseType >::length [private] |
TODO: potrebne?
BaseType strings::search::RollingHash< BaseType >::modulus [private] |
modulus of the hash function