4430
правок
Сходство между сжатыми строками: различия между версиями
Перейти к навигации
Перейти к поиску
м
Сходство между сжатыми строками (посмотреть исходный код)
Версия от 12:16, 4 июня 2022
, 4 июня 2022→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 114: | Строка 114: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью | Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью оптимальнее O(nm' + n'm) при вычислении сходства двух строк, закодированных при помощи длин серий [1, 11, 12]. Остается открытым вопрос о распространении этих результатов на метрику расстояния Левенштейна, метрику взвешенного расстояния редактирования и метрику аффинного штрафа за гэп. | ||