Developing.ru

Встала проблема сранения двух строк, но не просто нужно их сравнить, а найти отличия. Входные данные: эталонная строка и строка вводимая пользователем. В строке введённой пользователем нужно найти ошибки. Как подойти к решению? Нужно учесть что строки могут отличаться и по длине и по содержанию (от пользователя можно всего ожидать), возможны и "механические" ошибки при вводе, например, пропущен пробел между словами. Да, пользователю даётся возможность полностью ввести и, если нужно, отредактировать текст, проверка должна производиться только тогда, когда пользователь решил, что можно проверять. То есть, я хочу сказать, что ошибки не должны отлавливаться в процессе ввода. STL-вский алгоритм mistmatch, может быть и можно применить, но в контексте другого алгоритма.

Albor писал(а):Встала проблема сранения двух строк, но не просто нужно их сравнить, а найти отличия. Входные данные: эталонная строка и строка вводимая пользователем. В строке введённой пользователем нужно найти ошибки. Как подойти к решению? Нужно учесть что строки могут отличаться и по длине и по содержанию (от пользователя можно всего ожидать), возможны и "механические" ошибки при вводе, например, пропущен пробел между словами. Да, пользователю даётся возможность полностью ввести и, если нужно, отредактировать текст, проверка должна производиться только тогда, когда пользователь решил, что можно проверять. То есть, я хочу сказать, что ошибки не должны отлавливаться в процессе ввода. STL-вский алгоритм mistmatch, может быть и можно применить, но в контексте другого алгоритма.

Э-э... нужно создавать полный список ошибок? Скажем, тстовая строка "Ещё", пользователь ввел "Исчо" - что должно быть на выходе?

Нет, реакция на столь хорошее знание языка будет считаться как ошибка и данное слово будет зачёркнуто. Пончалу, мне эта задача казалась довольно простой, но именно пример со словом ЕЩЁ, почему-то тоже влез в голову и ослажнил жизнь. Кстати, это слово некоторые пишут как ЕСЧЁ.

Тогда напишите, что должно быть выходными данными.

Алгоритм должен определить все позиции в которых нет совпадения текста, естественно слова должны анализироваться на порядок следования. Если слово полностью не совпадает это ошибка одного типа, если пропущена буква, то другого и т.д. Нужно найти ошибки. Вопрос не стоит в том чтобы выдать готовый алгоритм. Больше нужны идеи как это решить.

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

Собственно, к подобному я и пришёл: поиск самой длинной совпадающей подстроки, а после - рекурсивный вызов для двух подстрок до и после найденной. Спасибо.

Если кому интересно, то полностью удовлетворяет данную тему алгоритм, называемый "Расстояние Левенштейна". Почитать о нём можно в Википедии, там и исходники есть на разных языках программирования. Снимаю шляпу перед математиками. Решение просто и гениально.