Найти метрику Левенштейна для двух строк

@Daos711 · Регистрация: 25.04.2020

Студворк — интернет-сервис помощи студентам

Метрика Левенштейна между двумя строками — это минимальное количество односимвольных правок (т. е. вставок, удалений или замен), необходимых для превращения одного слова в другое. Пример: для строк kitten и sitting получим преобразования kitten -> sitten -> sittin -> sitting. Значит для этих строк метрика равна 3. Нужно написать прогу, вычисляющую метрику для любых строк. Получилось пока так, но считает много лишнего, не хватает знаний понять, где ошибка

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def levenshtein(a,b):
    k = 0
    if len(a) > len(b):
        a = a[:len(b)]
        k += len(a) - len(b)
    elif len(a) < len(b):
        a = a + b[len(a):]
        k += len(b) - len(a)
    else:
        pass
    for ind1, val1 in enumerate(list(a)):
        for ind2, val2 in enumerate(list(b)):
            if ind1 == ind2 and val1 == val2:
                pass
            else:           
                a = a.replace(val1, val2)
                k += 1
    return k

@Catstail · 21.09.2023, 15:03

Вот тут описана удобная рекуррентная формула.

Новые блоги и статьи Все статьи Все блоги /
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .

@Catstail Супер-модератор 38195 / 21128 / 4309 Регистрация: 12.02.2012 Сообщений: 34,736 Записей в блоге: 14
	21.09.2023, 15:03
	Вот тут описана удобная рекуррентная формула. 1