Выяснить набор операций, которыми из строки1 можно получить строку2 -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [18.221.53.209]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Выяснить набор операций, которыми из строки1 можно получить строку2

Dart_Sitius

Сообщ. #1 , 03.02.17, 12:44

Member

Профиль · PM

Рейтинг (т): 2

Известны 2 строки. К примеру "xyz" и "XyZ". Нужно определить, как за наименьшее количество операций получить из первой вторую. В данном примере это можно сделать за 2 операции, 1 и 3 буквы преобразовать регистр. Или к примеру "xyz" и "xyza" - нужно добавить в конце букву a. "xyz" и "yxZb" - поменять местами первые две буквы, сменить регистр третьей, и добавить в конце b. "xyz" и "abc" - выдать ответ никак. "xyz" и "axyb" - удалить третью букву, добавить в начале и в конце a и b.

Если более формально:
На вход: 3 строки. "xyz" -> "xYz", "abc" -> "?"
На выход: какая строка получится из "abc", если к ней применить набор правил из примера.

Конечно, вариантов как из одной строки сделать другую может быть несколько, тогда желательно взять с наименьшим количеством операций, а если и их несколько то любой.
Мне кажется задача должна быть распространенной и иметь готовое решение. Подскажите, есть ли алгоритмы? И если нет, то в какую сторону копать

OpenGL	Сообщ. #2 , 03.02.17, 13:38
Lamer Профиль · PM Поощрения: 2 Dgm Рейтинг (т): 90	Всё зависит от набора операций. Например, если есть только вставка одного символа, его замена и удаление, то это расстояние Левенштейна

Dart_Sitius	Сообщ. #3 , 03.02.17, 13:49
Member Профиль · PM Рейтинг (т): 2	Цитата OpenGL расстояние Левенштейна Спасибо! Сообщение отредактировано: Dart_Sitius - 03.02.17, 13:50

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0170 ] [ 16 queries used ] [ Generated: 23.04.24, 09:42 GMT ]