Блог пользователя emli

Задача (помогите если не трудно)
Автор emli, 13 лет назад, По-русски
Сколько букв необходимо заменить в данном слове ,состоящем из (12-15)букв, чтобы получить три целых слова Mark
например: MassrkMarkMark--> 2.
  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

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