p431.ans1
======================
*l???

=================
p431.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;
};

bool match_classic(string pattern, string name) {
    int px = 0;
    int nx = 0;
    int next_px = 0;
    int next_nx = 0;
    while(px < (int)pattern.size() || nx < (int)name.size()) {
        if(px < (int)pattern.size()) {
            char c = pattern[px];
            if(c == '?') {
                if(nx < (int)name.size()) {
                    px++;
                    nx++;
                    continue;
                }
            } else if(c == '*') {
                next_px = px;
                next_nx = nx + 1;
                px++;
                continue;
            } else {
                if(nx < (int)name.size() && name[nx] == c) {
                    px++;
                    nx++;
                    continue;
                }
            }
        }
        if(0 < next_nx && next_nx <= (int)name.size()) {
            px = next_px;
            nx = next_nx;
            continue;
        }
        return false;
    }
    return true;
}

uint64_t char_masks[26];

bool match_bitwise(string pattern, string name) {
    const uint64_t mask_all = (1llu << ((uint64_t)name.size() + 1)) - 1llu;

    memset(char_masks, 0, sizeof(char_masks));
    for(uint64_t i = 0; i < (uint64_t)name.size(); i++) {
        char_masks[name[i] - 'a'] |= (1llu << i);
    }

    uint64_t mask = 1;
    for(char c: pattern) {
        if(c == '*') {
            mask = mask_all - ((mask & -mask) - 1llu);
        } else if(c == '?') {
            mask = (mask << 1llu);
        } else {
            mask = (mask & char_masks[c - 'a']) << 1llu;
        }

        mask = mask & mask_all;
        if(mask == 0) {
            return false;
        }
    }

    return mask & (1llu << (uint64_t)name.size());
}

bool match(string pattern, string name) {
    if(8 <= name.size() && name.size() <= 62) {
        return match_bitwise(pattern, name);
    } else {
        return match_classic(pattern, name);
    }
}

int n, m;
vector<string> a;

void read() {
    cin >> n >> m;
    a.resize(n + m);
    for(int i = 0; i < n + m; i++) {
        cin >> a[i];
    }
}

bool check_all(string p) {
    for(int i = 0; i < n + m; i++) {
        bool should_match = i < n;
        if(match(p, a[i]) != should_match) {
            return false;
        }
    }
    return true;
}

pair<bool, string> rec(string p, string suff_to_match) {
    if(suff_to_match.empty() && check_all(p)) {
        return {true, p};
    } else if(check_all(p + "*")) {
        return {true, p + "*"};
    } else if(suff_to_match.empty()) {
        return {false, ""};
    }

    for(int i = 0; i < (int)suff_to_match.size(); i++) {
        vector<string> options = {"*"};
        options[0].push_back(suff_to_match[i]);

        if(i == 0) {
            options.push_back(string(1, suff_to_match[i]));
            options.push_back("?");
        }

        string new_suff = suff_to_match.substr(i + 1);
        for(string mid: options) {
            auto [ok, ans] = rec(p + mid, new_suff);
            if(ok) {
                return {true, ans};
            }
        }
    }

    return {false, ""};
}

void solve() {
    // Some intuition on how globs / shell matching works is useful for this
    // problem. One good summary is: https://research.swtch.com/glob. The
    // algorithm we are going to use is the one where where we always maintain
    // the position of the last *, and whenever we fail matching, we refresh the
    // position to the last *. This is quadratic in worst case, but for the
    // given inputs works well. The core for our approach is that because all
    // inputs are short (<= 11 characters), it's likely that the answer will
    // also be short. Particularly, we can have at most 11 non-star characters.
    // And after each of them we can either have a star or not have one. There
    // is also no reason for having two stars in a row. Let's fix the shortest
    // string s in the first set. We know we have to match it, so let's try to
    // generate the set of all candidate patterns. One way is to backtrack it by
    // starting with an empty pattern, and incrementally either adding the first
    // available character, a ?, or a *. The issue comes from the fact that we
    // need to track what the "first available character" is when it comes to
    // stars. It's also unclear how to bound the complexity of this approach.
    // One way is to think of it as selecting a subset of L <= |s| characters
    // that will stay as is, then this implies that the rest of the |s| - L will
    // either be covered by a * or a ?. The naive way is that each of the |s| -
    // L characters can either be there or no, and then we have 2^(|s|+1)
    // possible gaps to put the *. This is already less than a few million, but
    // we are actually over-counting because it never makes sense to put two
    // stars in a row. This solution is fast enough to pass, but a nice
    // observation that can theoretically speed this up is to actually do a
    // bitwise wildcard matching algorithm that maintains a mask of prefixes of
    // the text that can be matched, and incrementally adds characters from the
    // pattern. However, in practice the classic greedy matching algorithm is
    // faster for this problem.

    string base = a[0];
    for(int i = 0; i < n; i++) {
        if(base.size() > a[i].size()) {
            base = a[i];
        }
    }

    auto [ok, ans] = rec("", base);
    if(ok) {
        cout << ans << endl;
    } else {
        cout << "OOPS" << endl;
    }
}

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;
}

=================
p431.in1
======================
2 2
list
tablexx
dataone
datatwo

=================
statement.txt
======================
431. Wildcards
Time limit per test: 2.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



You are given a list of files in a directory and need to match a specific subset of these files. You've decided to do that with a single string containing wildcards.

More precisely, each file name is a string consisting of lowercase English letters ('a' through 'z'). You want to craft a string consisting of lowercase English letters, asterisks ('*'), and question marks ('?'). An asterisk matches any sequence of letters (including empty). A question mark matches exactly one letter. See examples for further clarification.

Given a list of file names that you want to match and the list of file names that you don't want to match, output a string (which may include wildcards) that will achieve that.

Input
The first line of the input file contains two integers n and m (1 ≤ n, m ≤ 10) — the number of file names to match and the number of file names not to match, respectively. The next n lines contain file names to match, one per line, each no more than 11 characters long, without any whitespace expect newlines. The next m lines contain file names not to match in the same format. All file names in the input file are different.

Output
Output one string that will do the required matches. The length of that string must not exceed 100. If there're several possible solutions, output any. If there's no solution, output "OOPS" (without quotes) instead.

Example(s)
sample input
sample output
2 2
list
tablexx
dataone
datatwo

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