В качестве подготовки к олимпиаде по информатике (10 класс) была задана такая задача: дано слово и шаблон. Нужно узнать, подходит ли слово под этот шаблон. Слово - последовательность латинских букв, а шаблон может содержать еще и символы ? и *. Знак вопроса - на этом месте может стоять только один символ, на месте звездочек - последовательность символов, возможно, пустая. Пример:
Слово: iwjvjmcquurlgix
Шаблон: i**j*j*?u?u*
Ответ нет, так как между двумя буквами U должен быть хотя бы один символ.
Помогите решить, подтолкните на правильные мысли. То, что мне пришло в голову - нахождение наибольшей общей подпоследовательности через ДП (и потом проверка на равенство с шаблоном без символов ? и *), ясное дело, работает далеко не всегда. Есть ли у этой задачи какое-нибудь хоть чуть-чуть красивое решение, не через тонны кода на "реализацию" (моя вторая гениальная идея)? Гуглил и искал на хабре не мало. Пишу на C++.
Вам надо сверить шаблон, посимвольно, со словом.
Буква совпадает (? всегда совпадает) - переходим к следующей.
Не совпадает - переходим к запасному варианту, если они кончились - ответ "нет".
Запасные варианты создаются на звездочках - перебором, сколько символов может под ней скрываться.
Создайте абстракцию (класс, структуру) - состояние проверки шаблона на определенной букве, это будет и текущее состояние, и каждый из сохраненных вариантов.
Да, по науке это называется конечным автоматом.
Средний
