"Такой вот полезной штукой человечество обязано работам сотрудника Института прикладной математики им. М. В. Келдыша АН СССРВладимира Иосифовича Левенштейна."
Если верить Википедии, не совсем так, алгоритм решения задачи Левенштайна предложен Р. Вагнером (R. A.
Wagner) и М. Фишером (M. J. Fischer) в 1974 году
Кстати (из той же
Википедии): "Если к списку разрешённых операций добавить транспозицию
(два соседних символа меняются местами), получается расстояние Дамерау —
Левенштейна.
Для неё также существует алгоритм, требующий O(MN) операций. Дамерау
показал, что 80 % ошибок при наборе текста человеком являются
транспозициями" (грамотный, однако же, народ за бугром ;).
