3 ms·
Isn't that O(n∙m²)? for each string (n) for each char (n∙m) zero out char, compute hash (n∙m²)
by ahaferburg 8y ago
Isn't that O(n∙m²)?
for each string (n)
for each char (n∙m)
zero out char, compute hash (n∙m²)
- pedrosorio 8y agoIf you hand code your own hash function you can compute hash(string with zeroed out i-th character) from hash(string) in O(1) An example of such a hash is a polynomial hash (sum c_i * p^i modulo M, with p and M prime) such as the one used to explain https://en.m.wikipedia.org/wiki/Rabin–Karp_algorithm https://en.m.wikipedia.org/wiki/Rabin–Karp_algorithm
- cperciva 8y agoRight, I meant using a polynomial hash.