Hacker News Reader

Comment by cperciva | Hacker News Reader

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.

View on HN

Isn't that O(n∙m²)?

    for each string (n)
      for each char (n∙m)
        zero out char, compute hash (n∙m²)

If 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

Right, I meant using a polynomial hash.

Indeed, but I want an algorithm with deterministic O(nm) time.

Reply on news.ycombinator.com