Content deleted Content added
Chmduquesne (talk | contribs) |
m →The hash function used is wrongly referred to as a Rabin Fingerprint: added signature (Bot, where art thou?) |
||
Line 192:
Although the hash function described is indeed a rolling hash, this is NOT the original Rabin fingerprint. A Rabin fingerprint is the result of a modulo operation (rest of a division) of the hashed string, taken as a sequence of bits (not bytes), and interpreted as a polynomial over GF(2), by another polynomial irreducible over GF(2). This is NOT equivalent to a modulo operation with an actual prime number. Multiplications and Additions of polynomials over GF(2) do NOT equate to multiplications and additions over n-bits integers, mainly because there is no carry. See https://en.wikipedia.org/wiki/Rabin_fingerprint for a more detailed explanation. It contains a link to the original paper. The coefficients of the polynomial are the bits, not the bytes (this is not a typo).
Note that the pdf linked as a reference does NOT actually refer to the fingerprint function being used as a Rabin fingerprint, so it is correct. The Rabin Karp algorithm does not require using the Rabin Fingerprint, but any rolling hash will work. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Chmduquesne|Chmduquesne]] ([[User talk:Chmduquesne#top|talk]] • [[Special:Contributions/Chmduquesne|contribs]]) 11:32, 30 November 2017 (UTC)</small>
| |||