|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 03-2. Шаблон и слово.
(Разбор)
Для начала определим, какая из введенных строк является словом, а какая - шаблоном. Та строка, в которой есть символы '?' или '*' - шаблон. Если ни в одной из строк их нет, то в качестве шаблона возьмем произвольную. Будем определять, может ли часть слова (обозначим s1)с 1-го по k-й символ соответствовать части шаблона (обозначим s2)с 1-го по m-й символ (обозначим ak,m). Теперь есть 3 варианта:
- В шаблоне на m-м месте стоит буква. Тогда она соответствует последней букве слова и ak,m=(s1[k]=s2[m]) and ak-1,m-1
- В шаблоне на последнем месте стоит '?'. Тогда он соответствует последней букве слова и ak,m=ak-1,m-1
- В шаблоне на последнем месте стоит '*'. Тогда возможны два варианта: либо этой звездочке соответсвует пустая последовательность букв слова, либо непустая. Во втором случае в части слова с 1-го по k-1-й символ этой звездочке тоже соответствует некоторая последовательность букв (возможно пустая). Таким образом ak,m=ak-1,m or ak,m-1.
Осталось рассмотреть несколько моментов. Так как '*' может соответствовать пустая последовательность букв, то непустому шаблону вполне может соответствовать пустое слово, значит матрица a должна индексироваться не от 1, а от 0. Если же один из индексов отрицательный - то это всегда FALSE.
Заметим, что абсолютно аналогично можно решать задачу про соответсвие двух шаблонов. Просто добавятся еще несколько случаев.