Content deleted Content added
No edit summary |
|||
Line 68:
[[User:StTwister|StTwister]] 15:39, 25 January 2007 (UTC):
In order to be possible to change compute the hash of the next subsequence of S in constant time (to keep a low complexity), the hash must first be calculated outisde the loop entirely (with a 1 to M iteration) and then only updated inside the loop (remove the ith element from the hash and add the (i+m)-th element to the hash). So I think it's clearer if left this way.
CRCs are another possible rolling hash function. If you google "Rabin Hash", you'll find a SourceForge project implementing a CRC in Java (though they call it a Rabin fingerprint instead of a CRC).
== Some pseudocode fixes (both single and multiple pattern search) ==
| |||