Content deleted Content added
removed text from "multiple pattern search" |
|||
Line 28:
:I need to correct myself. The code is ok, although I don't quite get how the rolling hash would compare varying key-lengths. I improved the code indentation so the code is more readable [[User:ISee|iSee]]
==No worst case==
I removed the following text in the "multiple pattern search" section:
"We can also ensure O(''m'' ''n'' log ''k'') time in the worst case, where ''m'' is the length of the longest of the ''k'' strings, by storing the hashes in a [[self-balancing binary search tree]] instead of a hash table."
Rabin-Karp simply doesn't make sense in the worst case, because the whole idea of hashing requires randomization and can only work in expectation (or with high probability).
| |||