p237.ans1
======================
YES
abacaba

=================
p237.ans2
======================
NO

=================
p237.ans3
======================
YES
avtobusubotva

=================
p237.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string regex_str;

void read() { cin >> regex_str; }

void solve() {
    // First, '!' is just shorthand for "???", so we expand it and only have to
    // reason about letters, '?' and '*'. The core DP is dp[l][r], the minimum
    // length of a palindrome that the regex segment s[l..r] can produce. Since
    // the produced string is a palindrome, its first and last characters must
    // agree, and they come from s[l] and s[r] respectively (or, if either is a
    // '*', from that '*' absorbing one extra character). That gives a small
    // case split on (s[l], s[r]): when both are non-'*' we peel both ends with
    // a compatible outer char (letters force it, '?' is free); when one is
    // '*' and the other isn't, the '*' may match empty (drop and recurse) or
    // absorb the matching char on its side while staying in place; when both
    // are '*' either may match empty.
    //
    // Length-optimal moves can produce different palindromes, so for the
    // lex-smallest answer we have to actually compare the candidates rather
    // than rely on a heuristic ('prefer drop' / 'prefer peel' both have
    // counterexamples, e.g. "*bab*ba" needs drop but "*!ba*!" needs peel).
    // We therefore build the actual pal[l][r] string for every cell, in
    // increasing-length order. Each cell of length L depends only on cells
    // of length L-1 and L-2, so we keep just three rolling layers of strings
    // alive at any time, which caps memory at O(n^2) chars and stays well
    // under the limit even at n=765 after '!' expansion.

    string s;
    for(char c: regex_str) {
        if(c == '!') {
            s += "???";
        } else {
            s += c;
        }
    }

    int n = s.size();
    if(n == 0) {
        cout << "YES\n\n";
        return;
    }

    const int INF = INT_MAX / 2;
    vector<vector<int>> dp(n, vector<int>(n, INF));

    auto is_star = [&](int p) { return s[p] == '*'; };
    auto is_q = [&](int p) { return s[p] == '?'; };

    auto get_dp = [&](int a, int b) -> int {
        if(a > b) {
            return 0;
        }
        return dp[a][b];
    };

    for(int i = 0; i < n; i++) {
        dp[i][i] = is_star(i) ? 0 : 1;
    }

    for(int len = 2; len <= n; len++) {
        for(int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            int best = INF;

            if(is_star(l) && get_dp(l + 1, r) < INF) {
                best = min(best, get_dp(l + 1, r));
            }

            if(is_star(r) && get_dp(l, r - 1) < INF) {
                best = min(best, get_dp(l, r - 1));
            }

            if(!is_star(l) && !is_star(r)) {
                int inner = get_dp(l + 1, r - 1);
                bool ok = true;
                if(!is_q(l) && !is_q(r) && s[l] != s[r]) {
                    ok = false;
                }
                if(ok && inner < INF) {
                    best = min(best, inner + 2);
                }
            } else if(!is_star(l) && is_star(r)) {
                int inner = get_dp(l + 1, r);
                if(inner < INF) {
                    best = min(best, inner + 2);
                }
            } else if(is_star(l) && !is_star(r)) {
                int inner = get_dp(l, r - 1);
                if(inner < INF) {
                    best = min(best, inner + 2);
                }
            }

            dp[l][r] = best;
        }
    }

    if(dp[0][n - 1] >= INF) {
        cout << "NO\n";
        return;
    }

    vector<string> layer_a(n), layer_b(n), layer_c(n);
    vector<string>* lm2 = &layer_a;
    vector<string>* lm1 = &layer_b;
    vector<string>* cur = &layer_c;

    string answer;
    for(int len = 1; len <= n; len++) {
        for(int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            (*cur)[l].clear();
            if(dp[l][r] >= INF) {
                continue;
            }

            if(len == 1) {
                if(is_star(l)) {
                    (*cur)[l] = "";
                } else if(is_q(l)) {
                    (*cur)[l] = "a";
                } else {
                    (*cur)[l] = string(1, s[l]);
                }
                continue;
            }

            int target = dp[l][r];
            bool have = false;
            string best;

            auto try_cand = [&](string cand) {
                if(!have || cand < best) {
                    best = std::move(cand);
                    have = true;
                }
            };

            if(!is_star(l) && !is_star(r)) {
                int inner = (len == 2) ? 0 : dp[l + 1][r - 1];
                if(inner != INF && inner + 2 == target) {
                    bool ok = true;
                    char c = 0;
                    if(!is_q(l) && !is_q(r)) {
                        if(s[l] == s[r]) {
                            c = s[l];
                        } else {
                            ok = false;
                        }
                    } else if(!is_q(l)) {
                        c = s[l];
                    } else if(!is_q(r)) {
                        c = s[r];
                    } else {
                        c = 'a';
                    }
                    if(ok) {
                        const string& ip =
                            (len == 2) ? string() : (*lm2)[l + 1];
                        string cand;
                        cand.reserve(ip.size() + 2);
                        cand += c;
                        cand += ip;
                        cand += c;
                        try_cand(std::move(cand));
                    }
                }
            }

            if(!is_star(l) && is_star(r)) {
                int inner = dp[l + 1][r];
                if(inner != INF && inner + 2 == target) {
                    char c = is_q(l) ? 'a' : s[l];
                    const string& ip = (*lm1)[l + 1];
                    string cand;
                    cand.reserve(ip.size() + 2);
                    cand += c;
                    cand += ip;
                    cand += c;
                    try_cand(std::move(cand));
                }
            }

            if(is_star(l) && !is_star(r)) {
                int inner = dp[l][r - 1];
                if(inner != INF && inner + 2 == target) {
                    char c = is_q(r) ? 'a' : s[r];
                    const string& ip = (*lm1)[l];
                    string cand;
                    cand.reserve(ip.size() + 2);
                    cand += c;
                    cand += ip;
                    cand += c;
                    try_cand(std::move(cand));
                }
            }

            if(is_star(l) && dp[l + 1][r] == target) {
                try_cand((*lm1)[l + 1]);
            }

            if(is_star(r) && dp[l][r - 1] == target) {
                try_cand((*lm1)[l]);
            }

            (*cur)[l] = std::move(best);
        }

        if(len == n) {
            answer = std::move((*cur)[0]);
            break;
        }

        vector<string>* tmp = lm2;
        lm2 = lm1;
        lm1 = cur;
        cur = tmp;
        for(auto& x: *cur) {
            x.clear();
            x.shrink_to_fit();
        }
    }

    cout << "YES\n" << answer << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p237.in1
======================
abac?ba

=================
p237.in2
======================
a?dcaba


=================
p237.in3
======================
avtobus*


=================
statement.txt
======================
237. Galaxy X: Episode I - Masters of Mind
time limit per test: 0.25 sec.
memory limit per test: 16384 KB
input: standard
output: standard



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
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
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. Words must be written without quotes.

Sample test(s)

Input
Test #1
abac?ba

Test #2
a?dcaba

Test #3
avtobus*

Output
Test #1
YES
abacaba

Test #2
NO

Test #3
YES
avtobusubotva
Author:	Alexey Preobrajensky
Resource:	---
Date:	December, 2003

=================
