Редактировать: TL; версия DR: как получить все возможные обратные следы для расстояния Дамерау – Левенштейна между двумя словами?Я использую https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm, чтобы вычислить расстояние, и тривиальный алгоритм обратного следа (показанный ниже), чтобы восстановить список исправлений.
Более подробная информация ниже:
Только что застрял с оптимальным выравниванием струн (вроде расстояния Дамерау – Левенштейна) при попытке получить полный наборвозможных выравниваний.
Цель состоит в том, чтобы выровнять 2 строки для дальнейшего сравнения в алгоритме автоматического предложения.В частности, я хотел бы игнорировать вставки после конца первого слова.
Проблема в том, что в некоторых случаях возможно несколько «оптимальных» выравниваний, например,
align("goto", "go to home")
1) go to
go to home
2) go t o
go to home
К сожалению, моя реализация находит только второй вариант, а мне нужны оба или 1-й вариант.
Я пытался выполнить какой-либо поиск пути A * или BFS, но похоже, что матрица вычисления стоимости "настроена" только для (2) варианта.Ниже приведен скриншот, где я могу найти красный путь, но похоже, что зеленого пути нет: 
Однако кто-то сделал демо-версию, которая реализует именно то, что я хочу:
Что мне здесь не хватает?
Возможно, моя реализация слишком длинна, чтобы публиковать ее здесь, поэтому есть ссылка на github: https://github.com/victor-istomin/incrementalSpellCheck/blob/f_improvement/spellCheck.hpp
Реализация расстояния находится в методах optimStringAlignementDistance () и optimStringAlignmentBacktrace ().