News for hackers. Stuff that matters.
Re:A spellchecker used to be a major feat of software engine... by mattkrause on Thursday December 03, 2020 @07:40PM (#25297548)
Can't edit distance be computed in O(mn) time/space with dynamic programming?
Re:A spellchecker used to be a major feat of software engine... by zingermc on Thursday December 03, 2020 @09:24PM (#25298212)
Yes, at least for Levenshtein-style edits (substitution, insertion, deletion).

Although, I suppose a spell checker algorithm would be O(mnd) where d is the size of the dictionary, because it needs to compute O(mn) edit distance for each of the dictionary words.