3 ms·
It was not trivial to come up with an optimal and elementary O(nm) time algorithm. Compute the hashes of the nm strings formed by taking each of the n strings
by cperciva 8y ago
It was not trivial to come up with an optimal and elementary O(nm) time algorithm.
Compute the hashes of the nm strings formed by taking each of the n strings and zeroing out one of the m characters. If you get any hash collisions, compare the strings.
- ahaferburg 8y agoIsn'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.
- chaoxu 8y agoIndeed, but I want an algorithm with deterministic O(nm) time.