| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > Выяснить набор операций, которыми из строки1 можно получить строку2 |
| Автор: Dart_Sitius 03.02.17, 12:44 |
| Известны 2 строки. К примеру "xyz" и "XyZ". Нужно определить, как за наименьшее количество операций получить из первой вторую. В данном примере это можно сделать за 2 операции, 1 и 3 буквы преобразовать регистр. Или к примеру "xyz" и "xyza" - нужно добавить в конце букву a. "xyz" и "yxZb" - поменять местами первые две буквы, сменить регистр третьей, и добавить в конце b. "xyz" и "abc" - выдать ответ никак. "xyz" и "axyb" - удалить третью букву, добавить в начале и в конце a и b. Если более формально: На вход: 3 строки. "xyz" -> "xYz", "abc" -> "?" На выход: какая строка получится из "abc", если к ней применить набор правил из примера. Конечно, вариантов как из одной строки сделать другую может быть несколько, тогда желательно взять с наименьшим количеством операций, а если и их несколько то любой. Мне кажется задача должна быть распространенной и иметь готовое решение. Подскажите, есть ли алгоритмы? И если нет, то в какую сторону копать |
| Автор: OpenGL 03.02.17, 13:38 |
| Всё зависит от набора операций. Например, если есть только вставка одного символа, его замена и удаление, то это расстояние Левенштейна |
| Автор: Dart_Sitius 03.02.17, 13:49 |
| Цитата OpenGL расстояние Левенштейна Спасибо! |