Timeline for Reducing the time for rolling hash
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2022 at 4:28 | comment | added | greybeard | (The -96 is ill-conceived right from the start, just offsetting the sum by -96*len(P).) Multiplying the checksum with some constant before adding in another item is one way to get a position sensitive checksum, which would reduce the matches to just aab 4 in the example (in all likelihood: in general, there may be collisions with any fixed size summary of something unlimited in size). | |
| Aug 1, 2019 at 17:03 | vote | accept | Fiestyhokage | ||
| Aug 1, 2019 at 17:03 | |||||
| Aug 1, 2019 at 17:02 | vote | accept | Fiestyhokage | ||
| Aug 1, 2019 at 17:02 | |||||
| Aug 1, 2019 at 14:42 | comment | added | user555045 | @Ananthhokage well it's really simple, it comes down to that one line of code that I wrote above.. with suitable initialization of course. In general with a hash function that also involves multiplying the hash by a constant, there may be some trickier math concepts involved (modular multiplicative inverse etc) but the code is still really simple. | |
| Aug 1, 2019 at 14:37 | comment | added | Fiestyhokage | so i should learn rolling hash algorithm first? | |
| Aug 1, 2019 at 12:45 | comment | added | user555045 | @Ananthhokage using a rolling hash should help with the time | |
| Aug 1, 2019 at 12:21 | comment | added | Fiestyhokage | Thanks!This is not exactly the rolling hash algorithm , it was just named like that.The code i wrote works the way i wanted , its just that the time needs to reduced. | |
| Aug 1, 2019 at 11:25 | history | answered | user555045 | CC BY-SA 4.0 |