Здравствуйте, serghd, Вы писали:

S>Может кто сталкивался уже, в какую сторону будет правильно думать?

Лучше всего в сторону смены профессии

А если серьёзно, то в чём проблема? Берёшь у друзей конспект лекций, находишь тему "динамическое программирование" читаешь и делаешь

Если коротко, то заводишь множество трок чисел: (позиция в образце, позиция в слове из словаря, число уже допущенных ошибок".
На первом шагу в множество кладёшь всего одну тройку из трёх 0.
Потом в цикле пока в множестве остаётся хотя бы одна тройка делаешь следующее:

по текущему состоянию массива, строишь следующее. Каждую тройку чисел можно "продолжить" несколькими способами.
1) если символы в текущих позиция слова из словаря и образце, совпадают, можно на 1 увеличить обе позиции.
2) если число ошибок меньше лимита и образец ещё не закончился, можно увеличить на 1 позицию в образце и число ошибок
3) если число ошибок меньше лимита и слово из словаря ещё не закончилось, можно увеличить на 1 позицию в слове из словаря и число ошибок
4) если достигнут конец обоих слов ( и образца и слова из словаря), а лимит ошибок ещё не превзойдён, то мы нашли то, что ищем.

Соответственно продолжаешь (кладёшь в множество, соответствующее след. шагу алгоритма) все варианты продолжения.
И крутишь цикл, пока не найдёшь или множество след. шага не будет пустым.

Так как каждый шаг мы как минимум одну из позиций увеличиваем, то шагов будет не больше, чем длина образца и слова из словаря в сумме.
Так как у нас есть лимит на число ошибок, то "ширина" поиска будет ограничена константой, зависящей, как O(лимита). Так что алгоритм линейный по лимиту и длинам.

Да, то, что я описал выше не накладывает ограничение на то, Что вставки не могут идти подряд. Сам придумай, как его туда добавить.

Творческих узбеков и всё такое.

p. s.
Не благодари, в смысле для "спасибо" тут есть кнопки

Здравствуйте, serghd, Вы писали:

S>Может кто сталкивался уже, в какую сторону будет правильно думать?

Лучше всего в сторону смены профессии

А если серьёзно, то в чём проблема? Берёшь у друзей конспект лекций, находишь тему "динамическое программирование" читаешь и делаешь

Если коротко, то заводишь множество троек чисел: (позиция в образце, позиция в слове из словаря, число уже допущенных ошибок).
На первом шагу в множество кладёшь всего одну тройку из трёх 0.
Потом в цикле пока в множестве остаётся хотя бы одна тройка делаешь следующее:

по текущему множеству троек, строишь следующее. Каждую тройку чисел можно "продолжить" несколькими способами.
1) если символы в текущих позиция слова из словаря и образце, совпадают, можно на 1 увеличить обе позиции.
2) если число ошибок меньше лимита и образец ещё не закончился, можно увеличить на 1 позицию в образце и число ошибок
3) если число ошибок меньше лимита и слово из словаря ещё не закончилось, можно увеличить на 1 позицию в слове из словаря и число ошибок
4) если достигнут конец обоих слов ( и образца и слова из словаря), а лимит ошибок ещё не превзойдён, то мы нашли то, что ищем.

Соответственно продолжаешь (кладёшь в множество, соответствующее след. шагу алгоритма) все варианты продолжения.
И крутишь цикл, пока не найдёшь или множество след. шага не будет пустым.

Так как каждый шаг мы как минимум одну из позиций увеличиваем, то шагов будет не больше, чем длина образца и слова из словаря в сумме.
Так как у нас есть лимит на число ошибок, то "ширина" поиска будет ограничена константой, зависящей, как O(лимита). Так что алгоритм линейный по лимиту и длинам.

Да, то, что я описал выше не накладывает ограничение на то, Что вставки не могут идти подряд. Сам придумай, как его туда добавить.

Творческих узбеков и всё такое.

p. s.
Не благодари, в смысле для "спасибо" тут есть кнопки