Choice of MOD for rolling hash

Revision en1, by SamuelTull, 2023-12-06 14:00:21

For rolling hash, how do you decide which MOD to pick/ whether to use a tuple of 2 or more hashes? It is hard to know a priori whether the mod is high enough to prevent collisions / too high to cause memory limit / and multiple hashes could cause time limit. In This, 10**9 + 7 gave an incorrect answer, while 10**18 + 3 was accepted. Using a pair of hashes with 10**9 + 7 and 998244353 gave memory limit exceeded.

Tags rolling hashes

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SamuelTull 2023-12-06 14:04:52 7 Tiny change: 'sion/236031800) gave mem' -> 'sion/236032716) gave mem'
en1 English SamuelTull 2023-12-06 14:00:21 681 Initial revision (published)