|
Шаблоном называется строка, состоящая из английских букв (a..z, A..Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * - на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
Имеются 2 шаблона. Требуется найти длину строки минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
Исходные данные
Заданные шаблоны записаны в первых двух строках входного файла. Длина каждого шаблона не превышает 45 символов.
Результат
В выходной файл следует вывести длину строки минимальной длины, удовлетворяющей обоим шаблонам, либо сообщение "NO STRING"
Пример
| Исходные данные | Результат |
|---|
A*
*B | 2 |
Примечание. Действительно, строкой минимальной длины, удовлетворяющей шаблонам, является строка AB.
|
