Алгоритм коррекции строки в строку

Question

Я не уверен, что правильно назвал этот пост, но мне интересно, есть ли название для этого типа алгоритма:

Что я пытаюсь сделать, это создать минимальный набор инструкций для перехода от одной строки к ее перестановке , например, для

    STACKOVERFLOW -> STAKCOVERFLOW

потребуется минимум одна операция, то есть

    shift K before C.

Существуют ли в Интернете хорошие примеры

1. Нахождение минимального набора команд (я полагаю, это также часто называют расстоянием редактирования) и
2. Список инструкцийнабор

Спасибо!

Answer 1

Существует нечто, известное как расстояние Левенштейна, которое говорит вам, сколько изменений необходимо сделать для перехода от одной строки к другой, и есть много реализаций C #, а также многих других языков.

Вот вики:

http://en.wikipedia.org/wiki/Levenshtein_distance

Редактировать: Как указала TheHorse, расстояние Левенштейна не понимает изменений сдвига, но есть улучшенный алгоритм:

Расстояние Дамерау-Левенштейна