eolymp
bolt
Try our new interface for solving problems
Məsələlər

Два шаблона

Два шаблона

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Шаблоном называется строка, состоящая из английских букв {a, ..., z, A, ..., Z} и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * - на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблона, либо выдать сообщение, что такой строки не существует.

Giriş verilənləri

Заданные шаблоны записаны в первых двух строках входного файла.

Длина каждого шаблона не превосходит 80 символов.

Çıxış verilənləri

В выходной файл следует вывести длину строки минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "-1", если такой строки не существует.

Nümunə

Giriş verilənləri #1
A*
*B
Çıxış verilənləri #1
2