wtorek, 11 marca 2014

C++ standard inaccuracy

First we read:
21.4.1 basic_string general requirements [string.require]
3 No erase() or pop_back() member function shall throw any exceptions.
... few pages later: basic_string::erase [string::erase]
Allocator>& erase(size_type pos = 0, size_type n = npos);
2 Throws: out_of_range if pos > size().

SIMD-friendly Rabin-Karp modification

Rabin-Karp algorithm uses a weak hash function to locate possible substring positions. This modification uses merely equality of first and last char of searched substring, however equality of chars can be done very fast in parallel, even without SIMD instruction. Read more ...