Сколько букв необходимо заменить в данном слове ,состоящем из (12-15)букв, чтобы получить три целых слова Mark
например: MassrkMarkMark--> 2.
например: MassrkMarkMark--> 2.
ant.ermilov
|
13 лет назад,
#
|
+4
http://ru.wikipedia.org/wiki/Расстояние_Левенштейна
Ответом будет d(s,'MarkMarkMark')
→
Ответить
|
AndreySiunov
|
13 лет назад,
#
^
|
+3
Крутая вещь! А есть что-то более быстрое для вычисления этого расстояния? или только квадрат?
→
Ответить
|
ant.ermilov
|
13 лет назад,
#
^
|
0
Англоязычная вики предлагает несколько неасимптотических оптимизаций и одну идею для уменьшения времени до O(n*d), где d -- искомый ответ
→
Ответить
|