0234. Galaxy X: Episode I - Masters of Mind

Имя входного файла:	galaxy.in
Имя выходного файла:	galaxy.out
Ограничение по времени:	500 ms
Ограничение по памяти:	64 megabytes

Galaxy "X" greets you, the Masters of Mind Game. Are you ready to support your galaxy in battle for mind overwhelming? Are you ready to become Overminds? Are you brave enough to fight against the best of the best all-over-the-Universe mind-warriors? Then listen to me, Sons of Earth. That battle seems to be not too hard. Your mission is very simple. You must win at all costs. The Universal Mind contest begins…

The Universal Mind contest consists of several rounds, in which contestants solve logical, mathematical and other kinds of puzzles in fight for universal domination. We are not strong enough yet, and our galaxy can not get too much finance to stimulate our wishes and will to win. So, we do not need to win this contest (we simply are not able to do that truly heroical turn). All that we need is to pass the first round of contest (so called quarterfinals) and, probably, second (so called half-finals).

Our trainer N.A.Taskevich, found out (by using his special secret channels) that at the first round of the contest participants must, given a regular expression with special characters "*", "!" and "?", say the shortest palindrome (if answer is not unique, then you need to say lexicographically smallest one) that can be obtained by replacing special symbols with ordinary alphabet characters (small Latin letters from "a" to "z"), knowing the following rules of replacement:

• "*" is replaced by any number of any symbols from alphabet (possibly, zero symbols – empty string).
• "!" is replaced by exactly three symbols from alphabet.
• "?" is replaced by exactly one symbol from alphabet.

Palindrome is a string which does not change after reversing it (for example reversed string for "astalavista" is "atsivalatsa", so "astalavista" is not palindrome, but "abacaba" is palindrome, because its reversed string is "abacaba" too).

But even using all this, we currently do not fully understand logic of answers because we can not always say, whether answer is correct or not correct. To make some clearance about that, we need to write a program which determines a really correct answer (shortest lexicographically smallest one).

Input file

On the first line of input file there is a regular expression, consisting of ordinary alphabet characters (small Latin letters) and special characters ("*", "!" and "?"). The length of regular expression does not exceed 255.

Output file

On the first line of output file you must write single word "YES" (when it is possible to replace special characters to produce a palindrome) or "NO" (when it is impossible). In the case of positive answer, the second line of output file must contain the shortest lexicographically smallest palindrome which can be obtained from given regular expression.

Examples:

galaxy.in	galaxy.out
abac?ba	YES abacaba
a?dcaba	NO
avtobus*	YES avtobusubotva

Источник: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Обсудить       Отправить решение



Версия для печати